Battle with Upper Moon 6

Each test case has a grid with n rows and m columns, and initially every cell is alive. K contains each of 1 to n×m exactly once and gives the time at which each cell is killed. Process times 1 to n×m in order: first set the corresponding cell to dead, then revive all of its strict descendants. The children of cell (r,c) are the cells (r+1,c−1), (r+1,c), (r+1,c+1) that lie inside the grid, and descendants are the cells reachable recursively along child edges; an intermediate cell that is already alive still propagates, and the killed cell itself is not revived. Find the state after all operations, with alive as 1 and dead as 0. This site uses 0-based coordinates throughout, corrects typos in the source text's bottom-right corner and example coordinates, and keeps the original matrices and results.

输入格式

The first line contains T. Each test case first gives n m, then n lines, each with m values of K. Full original constraints: 1≤T≤1000, 1≤n,m≤1000; in each test case K is a permutation of 1..n×m; over all test cases Σ(n×m)≤10^6.

输出格式

In input order, output n lines for each test case, each containing m values 0 or 1 separated by spaces; test cases follow one another directly with no extra labels. 1 means alive at the end, and 0 means dead at the end.

样例 1

输入：

1
3 3
2 1 3
4 7 8
6 9 5

输出：

0 0 0
0 0 0
1 0 1

样例 2

输入：

1
3 1
3
1
2

输出：

0
1
1

样例 3

输入：

2
1 1
1
1 3
2 1 3

输出：

0
0 0 0

样例说明

In the original example, the first and third cells of the last row are revived by ancestor events that happen later, giving 000/000/101. In the second example, a single column [3,1,2], the top cell is killed last and revives the two cells below it; reviving only the direct child is wrong. The third example shows that the states of different test cases are independent.