Problem Description

Alice really likes binary. She thinks things are beautiful only if they are related to binary.

One day, she came up with a pattern on a whim, and plans to draw it on a grid whose height and width are both $2^n$. Each cell in the grid is either black or white, and initially all cells are white.

Now Alice defines a drawing operation as follows: choose a cell, and flip the colors of itself and its four adjacent neighbors (up, down, left, right). That is, black becomes white, and white becomes black.

Alice also states that the first row is adjacent to the last row, and the first column is adjacent to the last column.

Now Alice hopes you can provide an operation plan, or tell her that there is no solution. If there are multiple plans, output any one.

Input Format

The first line contains a positive integer $n$.

Then follows a $2^n \times 2^n$ matrix representing the pattern Alice wants. Here, $0$ means white and $1$ means black.

Output Format

The first line contains a number $\mathit{ans}$ indicating the number of operations, or output $-1$ if there is no solution.

Then output $\mathit{ans}$ lines, each containing a coordinate indicating an operation position. Each coordinate dimension ranges within $[0, 2^n - 1]$.

2
0 0 1 1
1 0 1 0
0 0 0 0
1 1 1 0

7
0 0
1 0
1 3
2 1
3 1
3 2
3 3

Hint

• For $20\%$ of the testdata, $n = 2$.
• For another $15\%$ of the testdata, $n = 4$.
• For another $15\%$ of the testdata, $n = 7$.
• For $100\%$ of the testdata, $n \leq 11$.

Translated by ChatGPT 5