Matrice Palindrom

Se dă o matrice binară pătratică $A$ de dimensiuni $N \times N$ cu elemente din mulțimea $\{0, 1\}$. Începi din celula $(0, 0)$ — colțul stânga-sus — cu un șir $S$, inițial gol, și vrei să ajungi în celula $(N − 1, N − 1)$ — colțul dreapta-jos. La fiecare mutare te poți deplasa în jos sau la dreapta cu o celulă. Pentru fiecare celulă prin care treci (inclusiv prima și ultima) adaugi valoarea din celula respectivă la capătul din dreapta al șirului $S$.

Cerință

Determinați dacă este posibil ca șirul $S$ astfel obținut să fie palindrom. Dacă da, determinați o succesiune de mutări în jos și/sau la dreapta care duce din celula $(0, 0)$ în celula $(N − 1, N − 1)$ pentru care șirul obținut este palindrom. Pentru această succesiune, determinați în ordine celulele parcurse.

Pentru că ne place de voi, am decis să vă anunțăm că matricea a fost generată aleator.

Date de intrare

Pe prima linie se află un singur număr întreg $N$, reprezentând latura matricii.

Următoarele $N$ linii conțin câte $N$ caractere din mulțimea $\{0, 1\}$, neseparate prin spații, reprezentând descrierea matricii.

Se garantează că matricea este aleasă uniform aleator dintre toate matricile binare de dimensiuni $N \times N$.

Date de ieșire

Afișați NO dacă nu se poate ca $S$ să fie palindrom. Altfel, afișați YES pe prima linie, apoi, pe fiecare dintre următoarele $2N − 1$ linii, afișați două valori, $i_k$ și $j_k \ (0 ≤ i_k, j_k < N )$ — coordonatele celei de-a $k$-a celule parcurse.

Restricții și precizări

• $1 \leq N \leq 5 \ 000$
• $A_{i, j} \in \{0, 1\}$ pentru $0 \leq i, j < N$

Exemplul 1

stdin

2
01
00

stdout

YES
0 0
0 1
1 1

Explicație

Obținem șirul 010, care este palindrom.

Exemplul 2

stdin

4
0100
1010
0100
0001

stdout

NO

Explicație

Nu se poate obține un șir palindrom.

Exemplul 3

stdin

4
0010
1001
1010
0010

stdout

YES
0 0
0 1
0 2
0 3
1 3
2 3
3 3

Explicație

Obținem șirul 0010100, care este palindrom.