CF1207B 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} $