Between classes, all of the boys are only talking about the World Cup, including the three heroes of this problem – Lazar, Momir and Uglješa. Every day, they argue about the best player, the best team, and most importantly, about who the winner will be. This final question – predicting the winner – always causes a huge argument. To settle this and find out who is the best at predicting match results, they agreed on a bet.

Each of them wants to predict the goal difference in the following \(N \cdot M\) matches. To make sure that the predictions are easy to read, Uglješa printed an \(N\) by \(M\) grid for each of them, where the cell \((i,j)\) (for \(1 \leq i \leq N\), \(1 \leq j \leq M\)) should contain the goal difference in the \(M\cdot(i-1)+j\)-th match. Note that the difference can be negative if the second team wins.

Momir has one secret that Lazar and Uglješa don’t know about: he doesn’t care for footbal at all! He didn’t watch a single World Cup match, and is just very good at making things up and nodding along. Now that he needs to make predictions, he is in big trouble. Luckily, he managed to catch a glimpse of his friends’ predictions, and saw Lazard’s grid \(l_{i,j}\) and Uglješa’s \(u_{i,j}\). Momir might not know anything about football, but he knows his friends, and knows that Lazar will underestimate the difference (he always plays it safe), while Uglješa will overestimate it (he is easily carried away). Therefore, Momir decided that his predictions \(m_{i,j}\) should satisfy \(l_{i,j} \leq m_{i,j} \leq u_{i,j}\).

To make thing smore interested, he turned the predictions into a game. He started by filling the grid with zeroes. He can then either increase all values in a single row by \(1\), or decrease all values in a single column bt \(1\). Your task is to figure out if he can create a grid satisfying \(l_{i,j} \leq m_{i,j} \leq u_{i,j}\) by following these steps.

Input format

The first line of standard input contains an integer \(T\), the number of testcases. \(T\) testcases follow, each of which has the following format:

The first line of a testcase contains two integers \(N\) and \(M\). The next \(N\) lines contain \(M\) integers each, the matrix \(l_{i,j}\) of Lazar’s predictions. After that, the next \(N\) lines also contain \(M\) integers each, the matrix \(u_{i,j}\) of Uglješa’s predictions.

Output format

For each testcase, your program should print DA if it is possible to create a satisfactory grid using the process described in the statement, and NO otherwise. If the answer is DA, it should be followed by \(N\) lines with \(M\) integers each: Momir’s prediction grid. If multiple such grids exist, your program can print any one of them.

Example

Input

2
2 2
1 -2
0 -3
4 0
1 -2
2 2
0 0
0 1
0 0
0 1

Output

DA
1 -2
1 -2
NE

Explanation

In the first testcase, if we increase both rows once, and decrease the second column three times, we will get a grid that satisfies the given inequalities. In the second testcase, there is no solution.

Constraints

• \(1 \leq T \leq10\)
• \(1\leq N\leq 300\)
• \(-2\times10^9\le l_{i,j}\le u_{i,j}\le2\times10^9\)

Testcases are split into five disjoint groups:

• In tests worth 15 points: \(N,M\le10\) and \(u_{i,j}-l_{i,j}\le1\) for all \(1\le i\le N\), \(1\le j\le M\)
• In tests worth 10 points: \(l_{i,j}=u_{i,j}\) for all \(1\le i\le N\), \(1\le j\le M\)
• In tests worth 15 points: \(l_{i,j}=u_{i,j}\) for all \((i,j)\) where \(i=1\) or \(j=1\).
• In tests worth 15 points: \(l_{i,j}=u_{i,j}\) for all \((i,j)\) that have the same parity.
• In tests worth 45 points: no additional constraints.