牛たちはチェッカーに熱中しています。楽しさは尽きませんが、終盤はとても苦手で、助けを求めています。

$N\times N$、$(4 \le N \le 30)$ の盤で、次の手番でゲームを終える最適な手順を求めます。駒は + のマスだけを動き、相手の駒を飛び越えて取り、飛び越えた駒はすぐ除きます。$N=8$ の例です：

- + - + - + - +
+ - + - + - + -
- + - K - + - +
+ - + - + - + -
- o - o - + - +
+ - K - + - + -
- o - + - + - +
+ - K - + - K -

K は Bessie のキング、o は相手の駒です。次は常に Bessie の番です。キングは任意の斜め方向に相手を連続で飛び越え、取った駒を除きます。この盤では左下のキングが相手の三駒すべてを続けて飛び越え、ゲームを終えます。動く K は >K< です。

- + - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ - + - + - + -     + - + - + - + -    + - + - + - + -     + - + - + - + -
- + - K - + - +     - + - K - + - +    - + - K - + - +     - + - K - + - +
+ - + - + - + -     + - + - + - + -    + ->K<- + - + -     + - + - + - + -
- o - o - + - +     - o - o - + - +    - + - o - + - +     - + - + - + - +
+ - K - + - + -    >K<- K - + - + -    + - K - + - + -     + - K ->K<- + -
- o - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ ->K<- + - K -     + - + - + - K -    + - K - + - K -     + - K - + - K -

左から初期状態、移動 1 後、移動 2 後、移動 3 後。

手順は次のマスを通ります：

  1 2 3 4 5 6 7 8
1 - + - + - + - +
2 + - + - + - + -
3 - + - K - + - +
4 + - * - + - + -
5 - o - o - + - +
6 * - K - * - + -
7 - o - + - + - +
8 + - K - + - K -

行、列。開始：$(8,3)$；移動：$(6,1)$、$(4,3)$、$(6,5)$。

入力の $N\times N$ 盤にゲームを終える手順があれば求めてください（存在する場合、実は一意です）。盤には少なくともキング一個と相手の駒一個があります。

入力

• 1 行目：整数 $N$。

• $2,\ldots,N+1$ 行目：$i+1$ 行目に -、+、K、o のいずれかの $N$ 文字で、有効な盤の $i$ 行目を表します。

出力

• 1 行目以降：不可能なら impossible を一行。可能なら各行に空白区切りの二整数で、勝つキングの順次の位置を出力します。

入出力例

入力 1

8
-+-+-+-+
+-+-+-+-
-+-K-+-+
+-+-+-+-
-o-o-+-+
+-K-+-+-
-o-+-+-+
+-K-+-K-

出力 1

8 3
6 1
4 3
6 5

問題作成者：Rob Kolstad、2008