Filling Grid Empty Cells with Nearest Building Height

You are given a grid of size \(n \times m\) where each cell either contains a building with a certain height or is empty (denoted by 0). Your task is to fill every empty cell with the height of the nearest building in terms of Manhattan distance. The Manhattan distance between cell \((x_1, y_1)\) and \((x_2, y_2)\) is given by \( |x_1 - x_2| + |y_1 - y_2| \).

If an empty cell can reach multiple buildings, the value from the building that is reached first in a multi‐source BFS propagation will be used. It is guaranteed that every grid will have at least one building cell.

Example:

Input:
3 3
1 0 2
0 0 0
3 0 4
Output:
1 1 2
1 1 2
3 3 4

</p>

inputFormat

The first line of input contains an integer \(T\), the number of test cases. For each test case, the first line contains two integers \(N\) and \(M\) representing the number of rows and columns of the grid. The next \(N\) lines each contain \(M\) space-separated integers representing the grid. A 0 indicates an empty cell, while any non-zero integer represents the height of a building.

outputFormat

For each test case, output the filled grid where each row is printed on a new line with the heights separated by a single space.

## sample

3
3 3
1 0 2
0 0 0
3 0 4
2 2
0 0
0 5
1 3
0 0 7

1 1 2
1 1 2
3 3 4
5 5
5 5
7 7 7

</p>