Special Positions (APCS 2023-06 Intermediate)

You are given a two-dimensional integer matrix \(A\) with \(n\) rows and \(m\) columns. Rows and columns are both numbered from 0, so the top-left position is \((0,0)\) and the bottom-right position is \((n-1,m-1)\).

The Manhattan distance between positions \((i,j)\) and \((r,c)\) is

Consider a position \((i,j)\) and let \(x=A_{i,j}\). Sum the values at all matrix positions whose Manhattan distance from \((i,j)\) is at most \(x\):

Position \((i,j)\) is called a special position if the remainder when \(S_{i,j}\) is divided by 10 is exactly \(x\); that is,

Find every special position. First output their count, then output their coordinates in increasing lexicographic order. Coordinate \((i_1,j_1)\) comes before \((i_2,j_2)\) if \(i_1<i_2\), or if \(i_1=i_2\) and \(j_1<j_2\).

Input

The first line contains two positive integers \(n\) and \(m\), the number of rows and columns.

Each of the next \(n\) lines contains \(m\) integers. The \(j\)-th integer on the \(i\)-th line is \(A_{i,j}\).

Constraints

• \(1\le n,m\le50\)
• \(0\le A_{i,j}\le9\)

Output

On the first line, output the number \(k\) of special positions.

Then output \(k\) lines. Each line contains two space-separated integers \(i\) and \(j\), representing a special position \((i,j)\). Coordinates are 0-based and must be listed in increasing lexicographic order.

If \(k=0\), output only 0 on the first line.

Scoring

Sample Input 1

1 8
1 2 3 4 5 6 7 8

Sample Output 1

1
0 5

Sample Explanation 1

Since there is only one row, the Manhattan distance from \((0,j)\) is simply the difference between column indices. Evaluating every position gives:

Thus, the only special position is \((0,5)\).

Sample Input 2

2 3
5 2 3
4 5 6

Sample Output 2

2
0 0
1 1

Sample Explanation 2

The sum of all matrix entries is 25. At every position in this \(2\times3\) matrix, \(x\) is large enough for the distance-\(x\) neighborhood to include the entire matrix. Therefore, every neighborhood sum is 25 and has remainder 5. Only \((0,0)\) and \((1,1)\) contain the value 5, so they are the special positions, already listed in lexicographic order.

Source

APCS June 2023, Programming Task 2; ZeroJudge k732, Special Positions; explanation by Yi-Che Wang.