問題文

縦横がそれぞれ $N$ マスの、計 $N^2$ マスからなるグリッドがあります。

$2$ 整数 $r, c$ に対して「マス $(r, c)$ 」で上から $r \bmod N$ 行目、左から $c \bmod N$ 列目のマスを表すことにします。
なお「$x \bmod N$」とは、$x = Nq + r$ なる整数 $q$ が存在し、かつ $0 \leq r < N$ をみたすような唯一の整数 $r$ です。$\scriptsize \; (x \in \Z)$

はじめ、マス $(r, c) \scriptsize \; (0 \leq r, c < N)$ は、$S_{r, c} =$ . のとき白で、$S_{r, c} =$ # のとき黒で塗られています。

ところで、操作と行動が $N^2$ 種類ずつあります。
それぞれ「操作 $(r, c)$」$\scriptsize \; (0 \leq r, c < N)$ と、「行動 $(r, c) $」$\scriptsize (0 \leq r, c < N)$ として区別します。

$4$ マス、マス $(r, c), (r - 1, c), (r, c - 1), (r - 1, c - 1)$ の色を順に反転する。(黒ならば白で、白ならば黒で塗り直す。)

なお、$N$ の値によっては同一のマスの色が何度も反転される場合があることを留意せよ。

$3$ 操作、操作 $(r, c), (r, 0), (0, c)$ を順に行う。

なお $r, c$ の値によっては同一の操作が何度も行われる場合があることを留意せよ。

uni くんは、これらの行動を、自由な順番で、あわせて $0$ 回以上 $N^2$ 回以下行うことができます。

uni くんの目標は、すべてのマスが白で塗られているようにすることです。
この目標を達成することができるかどうかを判定し、できるならばそのような操作手順を $1$ つ求めてください。

$N = 8$ の場合の例：

左から順に、行動 $(4, 5), (1, 1), (0, 5)$ によって(奇数回)反転されるマスを示します。

入力

入力は、以下の形式で標準入力より与えられる：

$N$
$S_{1,1}S_{1,2}\dots S_{1,N}$
$S_{2,1}S_{2,2}\dots S_{2,N}$
$\vdots$
$S_{N,1}S_{N,2}\dots S_{N,N}$

出力

答えを、次の指示に従って標準出力へ出力せよ：

• 目標が達成できないとき：-1 と一行に出力せよ。
• 目標が達成できるとき：
  • 非負整数 $T \; (T \leq N^2)$ を、答えとなる手順の長さ (行動の回数) とする。
  • $i \scriptsize \; (1 \leq i \leq T)$ 番目の行動が 行動 $(R_i, C_i) \scriptsize \; (0 \leq R_i, C_i < N)$ であるような $T$ 個の整数の $2$ つ組 $(R_1, C_1), (R_2, C_2), \dots, (R_T, C_T)$ を、$T$ とあわせて次の形式で出力せよ：

  $T$
  $R_1 \enspace C_1$
  $R_2 \enspace  C_2$
  $\vdots$
  $R_T \enspace C_T$

制約

• $1 \leq N \leq 10^\bold{3}$
• $N$ は整数
• $S_{i,j} \in \{$ .$, $ # $\} \scriptsize \; (1 \leq i, j \leq N)$

サンプル

7
..#.#..
.......
#.##..#
..#.#..
#..##.#
.......
..#.#..

2
3 3
4 4

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

1
1 1

3
###
#.#
###

-1