Image Filter

Interview

Time limit1sMemory limit1024 MB

Summary

For each cell of a heightmap, pick the prediction filter and residual with the smallest absolute error, breaking ties by the lexicographically smallest pair.

Level: Easy3 of 10
Topics: Implementation, Greedy
Solved: No attempts yet

Problem

Problem setters exchange data and verify each other's work when they prepare a contest. Setter B built all the data for a problem that uses heightmaps and was satisfied with it.

Only the verification step was left, and then B found a problem. The heightmaps were saved as 16-bit grayscale bitmaps without much thought, and the files were too large for setters to send to each other in real time.

To solve this, a bitmap compression method was designed that uses filters. Compression processes each cell in order. Let $H_{p,q}$ be the height at row $p$ and column $q$ of the heightmap. When the cell being compressed is at row $r$ and column $c$ , define

$A = H_{r,c-1}$ , or $0$ if that cell does not exist
$B = H_{r-1,c}$ , or $0$ if that cell does not exist
$C = H_{r-1,c-1}$ , or $0$ if that cell does not exist

Each height in the compressed image is expressed with one of the five filters in the table below. A compressed cell is written as the filter number and the difference between the height and the prediction made by that filter.

Number	Filter prediction
$0$	$0$
$1$	$A$
$2$	$B$
$3$	$(A + B)$ divided by $2$ , rounded down
$4$	$A + B - C$

For example, suppose the following $2$ by $2$ heightmap is given.

6 4
2 1

Consider how to express the 1 at the bottom right.

With filter $0$ , the difference from the prediction is $1 - 0 = 1$
With filter $1$ , the difference is $1 - 2 = -1$
With filter $2$ , the difference is $1 - 4 = -3$
With filter $3$ , the difference is $1 - (2 + 4)/2 = -2$
With filter $4$ , the difference is $1 - (2 + 4 - 6) = 1$

The total of the absolute differences over the whole compressed image must be minimized over all possible ways of choosing filters. If several choices reach the minimum, pick the one whose sequence of (filter number, difference) pairs is lexicographically smallest when the cells are listed from the top left in column order. Write a program that performs this compression.

Input

The input consists of $T$ test cases. The first line contains $T$ .

The first line of each test case contains the size of the heightmap, $R$ and $C$ ( $1 \le R \le 100$ , $1 \le C \le 100$ ), separated by a space. The heightmap has $R$ rows and $C$ columns. The next $R$ lines each contain $C$ integers $H_{i,j}$ ( $0 \le H_{i,j} < 2^{16}$ ), the pixel values of the heightmap, separated by spaces.

Output

For each test case, print $R$ lines. Each line contains $C$ pairs, separated by spaces, where each pair is the filter number used and the integer difference from that filter's prediction.

Examples1

Example 1

Input

3
2 2
6 4
2 1
3 3
0 0 0
0 100 0
0 0 0
4 5
0 0 0 0 0
0 100 50 50 0
0 50 100 50 0
0 0 0 0 0

Expected output

0 6 3 1
3 -1 0 1
0 0 0 0 0 0
0 0 0 100 0 0
0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 100 3 0 1 0 0 0
0 0 3 0 1 50 2 0 0 0
0 0 0 0 0 0 0 0 0 0