소들은 체커 게임에 열중합니다. 끝없이 즐기지만 끝내기는 매우 못해서 도움을 원합니다.

$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$번 줄의 $N$개 -, +, K, o 문자가 올바른 판의 $i$행을 나타냅니다.

출력

• 1번 줄부터: 불가능하면 impossible만 한 줄에 출력합니다. 가능하면 각 줄에 공백 구분 두 정수로 승리하는 킹의 연속 위치를 출력합니다.

예제

입력 1

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

출력 1

8 3
6 1
4 3
6 5

문제 작성자: Rob Kolstad, 2008