이기는 체커

소들이 체커에 단단히 빠졌습니다. 게임을 즐기는 것과 달리 끝내기에는 영 서툴러서 당신의 도움이 필요합니다.

$N \times N$ ($4 \le N \le 500$) 크기의 체커판이 주어집니다. 말을 놓을 수 있는 칸은 +, 나머지 칸은 -로 표시됩니다. 놓을 수 있는 칸에는 두 종류의 말이 있습니다. 베시의 킹은 K, 상대의 말은 o입니다. 다음 차례는 베시이며, 판에는 항상 킹이 최소 한 개, 상대 말이 최소 한 개 있습니다.

킹은 인접한 상대 말을 대각선으로 뛰어넘어 그 말 바로 너머의 빈 칸에 내려앉으며 잡습니다. 네 대각선 방향 모두 가능하며, 일반적인 체커의 점프와 같습니다. 뛰어넘긴 말은 즉시 판에서 제거됩니다. 킹은 한 턴에 여러 번 연속으로 점프할 수 있으며, 이기는 턴에서는 모든 이동이 점프입니다.

하나의 킹이 하나의 끊기지 않는 점프 연쇄로 상대의 말을 모두 잡을 수 있으면, 베시는 이번 턴에 게임을 끝냅니다. 점프는 내려앉는 칸이 판 안에 있고 비어 있을 때에만 (상대 말도 다른 킹도 없을 때에만) 유효합니다. 다른 킹은 움직이지 않으며, 내려앉을 칸을 막기만 할 뿐 절대 잡히지 않습니다.

예를 들어 아래 판($N = 8$)에서는 왼쪽 아래 킹이 상대 말 세 개를 차례로 뛰어넘어 게임을 끝낼 수 있습니다.

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

행은 위에서 아래로 $1$부터 $N$까지, 열은 왼쪽에서 오른쪽으로 $1$부터 $N$까지 번호를 매깁니다. 여기서 이기는 킹은 $8$행 $3$열에서 출발해 $(6, 1)$, $(4, 3)$, $(6, 5)$에 차례로 내려앉으며, 매 점프마다 상대 말을 하나씩 제거합니다.

이러한 게임 종료 순서가 존재한다면 찾아내는 프로그램을 작성하세요.

• 첫째 줄: 정수 $N$.
• $2$번째 줄부터 $N + 1$번째 줄까지: $i + 1$번째 줄에는 판의 $i$번째 행을 나타내는 $N$개의 문자가 있으며, 각 문자는 -, +, K, o 중 하나입니다. 판의 첫 줄은 항상 -로 시작합니다.

어떤 킹으로도 상대 말을 모두 잡을 수 없다면, 한 줄에 impossible을 출력합니다.

그렇지 않으면 사전순으로 가장 작은 승리 순서를 출력합니다. 이기는 킹이 지나는 각 칸을 — 출발 칸부터, 각 점프 이후의 칸까지 — 한 줄에 하나씩, 공백으로 구분된 두 정수 행 열(둘 다 1부터 시작)로 출력합니다.

모든 승리 순서는 상대 말 하나당 정확히 한 번의 점프를 포함하므로 줄 수가 모두 같아 "가장 작은"의 의미는 분명합니다. 두 후보 순서를 위에서부터 한 줄씩 비교하여, 처음으로 달라지는 줄에서 행이 더 작은 쪽을, 행이 같다면 열이 더 작은 쪽을 택합니다.