Task
A squirrel discovered a deposit of peanuts. The deposit has a weirder shape, as it is made of rows of rooms, each of them having rooms. The deposit has in total rooms situated on the grid. We know the number of peanuts present in each of the rooms from the matrix.
As the squirrel doesn’t like to see too many peanuts in a room or too few peanuts in another room, it will proceed as follows: from day , the squirrel will take all the rooms in which a maximal number of peanuts exists and moves exactly one peanut to every adjacent room.
The squirrel is now asking you the following question:
"How many peanuts will there be in each room after days?"
We need to answer to such questions the squirrel will give to us.
Input
The first line of the input contains , representing the number of tests we will need to solve ().
Each testcase will contain lines.
The first line of the test will contain (), the number of days corresponding to each step.
The following lines of the test will contain the grid, each of the lines having columns, representing the initial values of the matrix ().
For tests worth points, (, ).
For tests worth more points, ().
For tests worth more points, ().
For tests worth more points, ().
Output
Each test will have the grid corresponding to the answer for that particular test case.
Example
stdin
4
2
15 14 18
16 15 13
11 18 14
3
11 14 13
13 12 15
14 16 12
4
16 12 14
13 14 12
11 14 12
1
11 12 13
14 13 11
12 13 11
stdout
16 17 14
14 13 16
13 16 15
13 13 13
12 13 15
15 13 13
12 14 14
14 14 11
13 12 14
12 12 13
11 14 11
13 13 11