問題文

$N \times N$ の正方形グリッドがあります。最初、各マスは白または黒で塗られています。

次の操作を $0$ 回以上 $5 \times 10^5$ 回以下行って、全てのマスを白くすることは可能ですか？可能であれば操作列の一例を、不可能であれば -1 を出力してください。

• 一辺が $3$ 以上の奇数マスの部分正方形グリッドを選び、部分正方形グリッドの対角線上の全てのマスの色を反転させる。
  • より厳密には、$k \geq 1, k + 1 \leq r \leq N - k, k + 1 \leq c \leq N - k$ を全て満たす整数の組 $(k, r, c)$ を一つ選び、整数 $i\ (-k \leq i \leq k)$ を用いて $(r + i, c + i)$ または $(r + i, c - i)$ と表される $4k+1$ 個のマスの色を反転させる。

制約

• $3 \leq N \leq 500$
• $S_i$ は . および # のみからなる長さ $N$ の文字列

入力

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

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

グリッドの上から $i$ 行目、左から $j$ 列目のマスは、$S_i$ の $j$ 文字目が . のとき白、# のとき黒で塗られている。

出力

操作列の一例を、以下の形式で出力してください。

$T$
$k_1\ r_1\ c_1$
$k_2\ r_2\ c_2$
$\vdots$
$k_T\ r_T\ c_T$

ただし、各変数の意味は以下の通りです。

• $T$ は操作列の長さを表す、$0$ 以上 $5 \times 10^5$ 以下の整数
• $k_i, r_i, c_i$ は $i$ 番目の操作において選んだ $k, r, c$ の値

条件を満たす操作列が存在しない場合は -1 を出力してください。

最後に改行してください。

ビジュアライザ

出力結果のWeb版ビジュアライザがこちらで提供されています。

コンテスト中における、ビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。

また、ビジュアライザの仕様に関する質問は原則受け付けません。あくまで補助ツールとしてご利用ください。

サンプル

サンプル1

入力

5
..#.#
...#.
##.#.
.###.
##.##

出力

3
1 2 2
1 4 3
2 3 3

グリッドの状態は下図のように変化します。

3
.#.
..#
.#.

-1

サンプル3

入力

15
...............
.....#####.....
...#########...
.#############.
#..#########..#
###..#####..###
#####..#..#####
#..####.#######
###..##.#######
#######.#######
#######.#######
#######.#######
.######.######.
...####.####...
.....##.##.....

出力

66
1 12 6
1 13 11
1 5 2
1 14 4
1 6 9
1 14 13
1 11 2
3 8 11
1 6 13
2 6 3
1 4 11
1 5 8
2 3 5
4 11 10
4 9 11
1 10 4
1 10 13
1 3 6
2 4 3
1 4 6
2 8 3
1 8 5
1 12 2
1 12 8
2 3 9
2 4 6
1 14 11
4 6 5
1 11 11
3 12 4
5 8 6
3 7 8
1 11 7
1 10 6
2 8 4
1 9 9
1 11 14
1 12 3
1 2 2
1 14 10
1 11 4
1 5 5
1 3 11
2 9 4
1 7 8
1 10 5
4 11 7
1 12 14
1 9 10
1 11 13
1 5 12
1 12 4
2 7 4
1 8 14
1 7 12
3 4 12
1 6 14
1 7 14
2 13 3
1 9 6
1 7 3
2 9 3
2 3 13
2 7 3
4 5 5
2 12 7

入力のグリッドは以下の通りです。