Background

"No Go" is a very interesting board game.

As everyone knows, in Go, "qi" refers to the empty spaces adjacent to a connected block of pieces. Two pieces are considered adjacent if they are at the ends of a line on the board, meaning they are in the same connected block. For example, in the diagram below, the white pieces form four independent connected blocks, and the black pieces form one connected block, with the green dot being the only "qi" for the black piece's connected block:

"Capturing" refers to removing pieces from the board that have no "qi". In the diagram above, if the white player moves to the green dot, they can capture all the black pieces.

In Go, we aim to occupy as much territory and capture the opponent's pieces as much as possible. However, No Go is the opposite—it is a very peaceful game where neither player's move can result in any capturing, meaning any move cannot leave any connected block of pieces without qi. For example, the white player cannot move to the green dot in the diagram above.

If your move leaves the opponent with no valid moves, you win.

Problem Description

Xiao F is very interested in No Go, but he often loses, so he wants to create an AI to play the game for him.

However, creating an AI is too difficult for Xiao F, and the AI he painstakingly wrote was outperformed by his classmates' AIs!

Now, he wants you to help him implement a part of the AI's functionality—random simulation, because he believes your excellent program can optimize his AI.

You are given an $n \times n$ board, which may already have some pieces on it, but the current situation is guaranteed to be legal, i.e., no connected block is without qi; it is now black's turn to move, so the number of black and white pieces on the board is equal.

Your task is to sequentially designate a feasible move position for both black and white pieces randomly until the game cannot proceed and a winner is determined.

In formal No Go competitions, there are some prohibitive rules. However, since Xiao F plays a new type of No Go with a variable board size, we only need to consider the qi rules mentioned above.

Input Format

The input consists of:
- One line containing an integer $n$, representing the size of the board.
- The next $n$ lines, each containing a string of length $n$, describing the $i$-th row of the board.
- . represents an empty space.
- X represents a black piece.
- O represents a white piece.

Refer to the sample input for details.

The input guarantees that the initial board situation is legal, with an equal number of X and O.

Output Format

You need to output at least one line. If you output $L$ lines, then for the first $L - 1$ lines, you should output two space-separated integers representing the move coordinates $x_i, y_i$, where odd-numbered lines represent black's moves and even-numbered lines represent white's moves. The $x$ coordinate ranges from $1$ to $n$ from top to bottom, and the $y$ coordinate ranges from $1$ to $n$ from left to right.

Please output -1 -1 on the $L$-th line, indicating that the $L$-th player has no valid moves.

Your output may be large, so even with a 3-second time limit, please avoid using slow methods to output a large amount of content.

Scoring Method:

This problem uses a Special Judge and partial scoring. We will score as follows:
- If your output format is incorrect, you will receive no points for that test case. Format errors include but are not limited to: outputting non-numeric content; outputting more or fewer than two integers per line; outputting coordinates outside the board; the last line not being -1 -1.
- If your output format is correct but the first line of your output is unacceptable, you will receive no points. For example: outputting coordinates that black cannot move to; black has valid moves but outputs -1 -1.
- If your output format is correct and the first $k (1 \leq k < L)$ lines of your output are acceptable, you will at least get $s$ points, where $s = \lfloor \lg k \rfloor + 1$, meaning $k$ is a number with $s$ digits in decimal representation.
- If your output is completely correct, regardless of how many lines you output, you will receive 10 points.

Refer to the sample explanation for details.

Sample Input and Output

Sample Input #1

3
XXX
OOX
OO.

Sample Output #1

-1 -1

Sample Input #2

3
XOO
XO.
X..

Sample Output #2

2 3
-1 -1

Notes

Sample 1 Explanation:

Noticing that filling the board will leave all connected blocks without qi, black has no valid moves.

Sample 2 Explanation:

There are two other correct outputs for Sample 2:

3 2
2 3
-1 -1

3 3
2 3
-1 -1

We represent the board as follows:

Among them, black can move to any of the three empty spaces.

• If black moves to $(2, 3)$, as shown, white has no valid moves:
  

• If black moves to $(3, 2)$, as shown, white's only valid move is $(2, 3)$, after which black has no valid moves:
  

• If black moves to $(3, 3)$, as shown, white's only valid move is $(2, 3)$, after which black has no valid moves:
  

Any of these outputs will earn full points.

Scoring Rules Explanation:

To explain the scoring rules, we use Sample 2 as an example. For the following outputs:

I AK IOI

Unfortunately, because you are too strong, we will give you 0 points to calm you down.

-1 -1

1 1
-1 -1

Unfortunately, your first line is not correct, so you get 0 points.

3 3
-1 -1

Your first line is part of a correct solution. Since 1 is a 1-digit number, congratulations, you get 1 point!

见题面 Input 部分

见题面 Output 部分