Problem M: Fissure Puzzle Hard

Problem

$N \times N$個のマスから成るグリッドがある。最初すべてのマスは白色である。以下の手順に従って黒色のマスを増やしていく。

上から偶数番目かつ、左から偶数番目であるマスの中で、白色のマスを1つ選ぶ。選んだマスは黒色に変化する。さらに、そのマスの上下左右それぞれの方向について、隣接している白色のマスも連鎖的に黒色に変化する。この連鎖はその方向に白色のマスが存在しなくなるまで続く。(以下に例を示す)

â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡â–¡
↓上から4番目、左から6番目を選ぶ
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
â– â– â– â– â– â– â– â– â– 
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
↓上から2番目、左から2番目を選ぶ
â–¡â– â–¡â–¡â–¡â– â–¡â–¡â–¡
â– â– â– â– â– â– â–¡â–¡â–¡
â–¡â– â–¡â–¡â–¡â– â–¡â–¡â–¡
â– â– â– â– â– â– â– â– â– 
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â–¡â–¡
↓上から6番目、左から8番目を選ぶ
â–¡â– â–¡â–¡â–¡â– â–¡â–¡â–¡
â– â– â– â– â– â– â–¡â–¡â–¡
â–¡â– â–¡â–¡â–¡â– â–¡â–¡â–¡
â– â– â– â– â– â– â– â– â– 
â–¡â–¡â–¡â–¡â–¡â– â–¡â– â–¡
â–¡â–¡â–¡â–¡â–¡â– â– â– â– 
â–¡â–¡â–¡â–¡â–¡â– â–¡â– â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â– â–¡
â–¡â–¡â–¡â–¡â–¡â– â–¡â– â–¡

あなたは上から$i$番目で左から$j$番目のマスの色が$A_{i,j}$であるグリッドを作りたい。 作ることが可能かどうかを判定せよ。可能な場合は、選ぶべきマスの場所と順番を求めよ。

Input

入力は以下の形式で与えられる。

$N$
$A_{1,1}$ $A_{1,2}$ ... $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ ... $A_{2,N}$
...
$A_{N,1}$ $A_{N,2}$ ... $A_{N,N}$

$A_{i,j}$が'o'であるときは上から$i$番目、左から$j$番目のマスが白色であることを表し、'x'のときは黒色のマスであることを表す。

Constraints

入力は以下の条件を満たす。

• $3 \le N \le 2047$
• $N$は奇数である
• $A_{i,j}$は'o'か'x'である

Output

不可能な場合は-1と1行に出力せよ。 可能な場合は1行目に選ぶマスの個数を出力し、 $i \times 2$行目には$i$番目に選択するマスが上から何番目なのかを、 $i \times 2 + 1$行目には$i$番目に選択するマスが左から何番目なのかを出力せよ。 一意に定まらない場合は辞書順で最小になるようにせよ。

Sample Input 1

5
oxooo
oxooo
oxooo
xxxxx
oxooo

Sample Output 1

1
4
2

Sample Input 2

9
oxoooooxo
oxxxxxxxx
oxoooooxo
xxxxxxxxx
oxoxooooo
oxxxxxxxx
oxoxoxooo
oxoxxxxxx
oxoxoxooo

Sample Output 2

4
4
2
2
8
6
4
8
6

Sample Input 3

3
oxx
oxx
ooo

Sample Output 3

-1