Quento

Quento is a game made by Q42. The board is always 3×3. As in the picture above, a black square holds a digit and a white square holds + or -. A square is a digit square when the sum of its row index and column index is even, and a symbol square when that sum is odd.

Above the board you are given the number N to build and the count M of digits you must use. You start on a digit square, swipe to a symbol square, swipe back to a digit square, and continue in that order. A swipe moves to a square that touches the current one horizontally or vertically. Diagonal moves are not allowed. A square you have already passed cannot be passed again. When you have passed M digit squares this way, the result must be N.

The expression is evaluated from left to right. If the digits you pass are $a_1, a_2, \dots, a_M$ in order and the symbols are $s_1, \dots, s_{M-1}$, then $(((a_1 \, s_1 \, a_2) \, s_2 \, a_3) \dots) \, s_{M-1} \, a_M$ must equal N. An intermediate value may be negative.

For example, to build 7 with two digits, 4+3 and 9-2 both work. 5+3-1 does not, because it uses three digits.

You are given N, M, and the digits and symbols written on the board. Write a program that finds a way to build N with M digits.

The first line contains N and M. ($1 \le N \le 45$, $2 \le M \le 5$) Each of the next three lines contains one row of the board as a string of length 3. Every digit is between 1 and 9.

Print 1 on the first line if N can be built with M digits, and 0 otherwise.

If it can be built, print the coordinates of the squares you pass on the next $2M-1$ lines, one square per line in visiting order. Each line holds the row index and the column index separated by a space. The top left square is (0, 0), the bottom left square is (2, 0), the top right square is (0, 2), and the bottom right square is (2, 2).

If several ways exist, print the one whose coordinate sequence $(r_1, c_1, r_2, c_2, \dots)$, written in visiting order, is smallest in lexicographic order.

You can download this game and play it yourself.

http://quento.com/