Alice is very fond of binary, believing that things are only beautiful if they are related to binary.

One day, she conceived of a pattern and planned to draw it on a grid of size $2^n \times 2^n$. The grid cells are either black or white, and they are all initially white.

Alice defines a painting operation as follows: select a cell, and invert the color of that cell and its adjacent cells (up, down, left, and right). That is, black becomes white, and white becomes black.

Alice also specifies that the first row and the last row of the grid are adjacent, and the first column and the last column are adjacent.

Now, Alice wants you to provide an operation sequence or report that no solution exists. If there are multiple solutions, you may output any one of them.

Input

The first line contains a positive integer $n$.

The next $2^n \times 2^n$ matrix represents the pattern Alice wants, where $0$ represents white and $1$ represents black.

Output

The first line contains an integer $ans$ representing the number of operations, or output $-1$ if no solution exists.

The next $ans$ lines each contain a coordinate representing an operation position. Each coordinate dimension is in the range $[0, 2^n - 1]$.

Examples

Input 1

2
0011
1010
0000
1110

Output 1

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

Constraints

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