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

Note

Link

 

---