A14519. Square Filling

You are given two matrices $A$ and $B$ . Each matrix contains exactly $n$ rows and $m$ columns. Each element of $A$ is either $0$ or $1$ ; each element of $B$ is initially $0$ .

You may perform some operations with matrix $B$ . During each operation, you choose any submatrix of $B$ having size $2 \times 2$ , and replace every element in the chosen submatrix with $1$ . In other words, you choose two integers $x$ and $y$ such that $1 \le x < n$ and $1 \le y < m$ , and then set $B_{x, y}$ , $B_{x, y + 1}$ , $B_{x + 1, y}$ and $B_{x + 1, y + 1}$ to $1$ .

Your goal is to make matrix $B$ equal to matrix $A$ . Two matrices $A$ and $B$ are equal if and only if every element of matrix $A$ is equal to the corresponding element of matrix $B$ .

Is it possible to make these matrices equal? If it is, you have to come up with a sequence of operations that makes $B$ equal to $A$ . Note that you don't have to minimize the number of operations.

The first line contains two integers $n$ and $m$ ( $2 \le n, m \le 50$ ).

Then $n$ lines follow, each containing $m$ integers. The $j$ -th integer in the $i$ -th line is $A_{i, j}$ . Each integer is either $0$ or $1$ .

If it is impossible to make $B$ equal to $A$ , print one integer $-1$ .

Otherwise, print any sequence of operations that transforms $B$ into $A$ in the following format: the first line should contain one integer $k$ — the number of operations, and then $k$ lines should follow, each line containing two integers $x$ and $y$ for the corresponding operation (set $B_{x, y}$ , $B_{x, y + 1}$ , $B_{x + 1, y}$ and $B_{x + 1, y + 1}$ to $1$ ). The condition $0 \le k \le 2500$ should hold.

The sequence of operations in the first example:

$\begin{matrix} 0 & 0 & 0 & & 1 & 1 & 0 & & 1 & 1 & 1 & & 1 & 1 & 1 \\ 0 & 0 & 0 & \rightarrow & 1 & 1 & 0 & \rightarrow & 1 & 1 & 1 & \rightarrow & 1 & 1 & 1 \\ 0 & 0 & 0 & & 0 & 0 & 0 & & 0 & 0 & 0 & & 0 & 1 & 1 \end{matrix}$