Kchess

O matrice $A$ se numeste $\text{Kchess board}$ daca este construita recursiv dupa regula:

• Se incepe cu o matrice de dimensiune $1 \cdot 1$, primul element al matricei este colorat alb
• Fie $B \ \ = \ \ \begin{pmatrix} A & A' \\ A' & A \end{pmatrix}$, unde $A$ este matricea generata la pasul anterior, iar $A'$ contine toate elementele din matricea originala, inversand culoarea fiecarui element (din alb in negru si invers). La final $A := B$.

Acest proces se repeta de $k$ ori.

Cerință

Fie $A$ o matrice $\text{Kchess}$. Un subset de elemente din matrice au culoarea schimbata fata de cum ar fi trebuit sa fie. Puteti sa alegeti un drum aproape perfect$^{\dagger \dagger}$, astfel incat daca interschimbati culorile elementelor care apartin de drum, tabla sa devina $\text{Kchess}$?

Date de intrare

Pe prima linie se afla $k$, urmat de o matrice patratica cu latura $2^k$. Fiecare element al matricei este $0$ (pentru alb) sau $1$ (pentru negru).

Date de ieșire

Se va afisa $P$, lungimea drumului, impreuna cu pozitiile elementelor din drum, fiecare pe cate un rand nou. In cazul in care nu exista solutie, se va afisa $-1$.

Restricții și precizări

• $^{\dagger \dagger}$ Un drum aproape perfect reprezinta o succesiune de pozitii distincte ale matricei, unde oricare $2$ elemente adiacente din drum au o latura comuna (pe verticala sau orizontala).
• Se garanteaza ca pentru fiecare element care apartine de drum, vor exista maxim $3$ vecini care sunt la randul lor inclusi in drum.
• $1 \leq k \leq 10$.

Exemplul 1

stdin

3
1 1 0 1 0 1 1 0 
0 0 1 1 0 1 1 1 
0 0 1 1 0 1 1 1 
1 1 0 1 1 1 0 0 
0 0 0 0 1 0 1 1 
1 0 1 0 1 0 0 0 
0 0 1 1 0 1 0 0 
1 1 1 0 0 0 0 1 

stdout

37
1 1
2 1
3 1
4 1
5 1
6 1 
6 2
7 2 
8 2 
8 3 
8 4
7 4
7 5
7 6
8 6
8 7
8 8
7 8
6 8
5 8
4 8
3 8
2 8 
1 8
1 7
1 6
1 5
1 4
1 3 
2 3
3 3
4 3
4 4 
5 4 
5 5 
5 6
4 6

Explicație

Exemplul 2

stdin

3
0 1 1 0 1 0 0 1 
1 0 1 0 1 1 1 0 
1 1 1 1 1 0 1 0 
0 0 1 0 1 1 1 1 
1 1 1 0 0 1 0 0 
0 1 1 1 1 0 1 1 
0 0 0 1 1 0 1 1 
1 1 1 0 1 0 0 0

stdout

26
3 2
4 2
5 2
5 3
5 4
6 4
7 4 
7 3 
7 2 
8 2
8 3 
8 4
8 5
8 6 
8 7 
7 7 
6 7
5 7
4 7 
4 6
3 6
3 5
2 5
2 4
2 3
3 3