A ski resort has slopes of steepness levels, numbered from to (a higher number means a steeper slope), and length levels, numbered from to (a higher number means a longer slope). A slope with steepness level and length level is said to have type .
Every skier has two limits: the maximum steepness level and the maximum length level that they agree to ride (1 \le x \le n, 1 \le y \le m). A skier with limits finds a slope of type suitable if i \le x and j \le y. Different skiers may have the same limits.
The resort ran a survey: for every slope type it is known how many skiers find it suitable, and this number is a_{i, j}. The list of skiers is lost. For every pair of limits , find how many skiers have exactly these limits, or report that the survey is inconsistent, that is, no set of skiers leads to these numbers.
The first line contains a single integer (1 \le t \le 100) — the number of test cases.
The first line of each test case contains two integers and (1 \le n, m \le 1000) — the number of steepness levels and the number of length levels.
The -th of the next lines contains integers a_{i, 1}, a_{i, 2}, \ldots, a_{i, m} (0 \le a_{i, j} \le 10^9) — the numbers of skiers who find the slopes with steepness level and length levels 1, 2, \ldots, m suitable.
The sum of n \cdot m over all test cases does not exceed 10^6.
For each test case, if the survey is inconsistent, print a single line with the number .
Otherwise print lines with numbers each: the -th line must contain c_{x, 1}, c_{x, 2}, \ldots, c_{x, m}, where c_{x, y} is the number of skiers with limits .
Example 1
In the first test case there are four skiers: one with limits , two with limits and one with limits . In the figure, the slopes suitable for each of these kinds of skiers are outlined on the left, and the answer is on the right. For example, the slope of type is suitable for all of them, that is, for 1 + 2 + 1 = 4 skiers, and the slope of type is suitable only for the two skiers with limits .