FastPrep

Description

Solutions

Battle with Upper Moon 6

📚RELATED PROBLEMS

In the older days, Douma was an upper moon 6. And as we all know the ability of upper moon 6 was that it doesn't die unless all of its versions are dead. Only Akaza knows how to kill Douma's versions, but as he is the biggest fan of Douma he wouldn't do it, so the demon slayer corps asked Shinobu Kocho to hypnotize him in order to avenge her sister's death.

So there is a grid with n rows and m columns where in each cell there is a Douma's version(a demon). The grid is numbered with (0,0) as the top left corner and (n, m) as the bottom right corner. The demons in cells (i + 1, j - 1), (i + 1, j), and (i + 1, j + 1) are called the children of the demon in cell (i, j). And we have a matrix K with n rows and m columns which tells in which turn which cell's demon will be killed by Akaza. So the demon in cell (i,j) will be killed in the K(i,j) th turn. But, if there is a catch, because of Douma's great regenerative abilities, when the demon of cell (i, j) dies, the children demons of this cell get alive anyway were dead at all and similarly the children of demons in cells (i + 1, j - 1), (i + 1, j) and (i + 1, j + 1) also get alive and the process continues. So basically the demon in cell (i,j) dies and the entire sub-tree's demons get alive if any were dead at all.

Hashiras are very curious if the given matrix K will be able to kill all the demons or not. Can you help the Hashiras know the state of every cell's demon after Akaza has executed the matrix K.

Print a space separated matrix where each cell will be 1 if the demon in that cell will be alive after all operations are executed successfully and 0 otherwise.

Note: There is one demon in each cell and all are alive in the beginning.

Input Format:

First line contains a single integer T which denotes the number of test cases. Then the first line of every test case will contain 2 space separated integers n, m denoting the dimensions of K. Then lines will follow and each line will contain m space separated integers denoting the order of killing. The jth integer of the ith line will tell at what number will the demon of cell (i, j) will be killed.

Output Format:

For each test case print n lines and each line should have m space separated integers. The jth integer of the ith line will be 1 if the demon at that cell will be alive after executing the killing process as per the order specified in the matrix K or 0 otherwise.

Constraints:

For all test cases

1 <= T <= 1000
1 <= K (i, j) <= n*m for all valid i,j
All elements of matrix K are pairwise distinct

For test cases worth 20% of total score

1 <= n, m <= 10 ^ 3
Sum of n * m across all test cases will not exceed 10 ^ 3

For test cases worth 50% of total score

1 <= n, m <= 500
Sum of n * m across all test cases will not exceed 10 ^ 5

For test cases worth 100% of total score

1 <= n, m <= 10 ^ 3
Sum of n * m across all test cases will not exceed 10 ^ 6

Example 1:

Input:  n = 3, m = 3, K = [[2, 1, 3], [4, 7, 8], [6, 9, 5]]
Output: [[0, 0, 0], [0, 0, 0], [1, 0, 1]] 
Explanation:
      
      Initially the demon grid will look like this:
      
      1 1 1
      1 1 1
      1 1 1
      
      

      
      And then the demon in the cell (1, 2) gets killed as K(1,2) = 1 looks like this: and all the demons in its subtree will be get alive. So the demon grid looks like this:
      
      1 0 1
      1 1 1
      1 1 1
      
      

      
      And this process continues to achieve the final grid.

Constraints:

See problem statement above :)