Array Play

There is a two-dimensional integer array $A$ with $N$ rows and $N$ columns. $A[r, c]$ denotes the value of the element in row $r$ and column $c$.

Consider a game on this array that applies a total of $M$ operations.

Each operation is given by five integers $(r_1, c_1, r_2, c_2, v)$ satisfying $1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le N$, and $-1{,}000 \le v \le 1{,}000$. The operation adds $v$ to every $A[r, c]$ inside the rectangle from $(r_1, c_1)$ to $(r_2, c_2)$.

For example, take $N = 3$ and $A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]$, and apply the following three operations in order.

• Operation 1: $(r_1 = 1, c_1 = 1, r_2 = 2, c_2 = 3, v = 3)$
• Operation 2: $(r_1 = 2, c_1 = 2, r_2 = 3, c_2 = 2, v = -5)$
• Operation 3: $(r_1 = 1, c_1 = 1, r_2 = 3, c_2 = 2, v = 1)$

Before any operation, $A$ is as follows.

A = [ [ 1 2 3 ]
      [ 4 5 6 ]
      [ 7 8 9 ] ].

Applying operation 1 changes the six elements in the first two rows:

A = [ [ 4 5 6 ]
      [ 7 8 9 ]
      [ 7 8 9 ] ].

After applying operation 2:

A = [ [ 4 5 6 ]
      [ 7 3 9 ]
      [ 7 3 9 ] ].

After applying operation 3:

A = [ [ 5 6 6 ]
      [ 8 4 9 ]
      [ 8 4 9 ] ].

After all three operations, you want the sum of the elements of each row and the sum of the elements of each column of the resulting array. In the example above, the row sums are $[17, 21, 21]$ (row 1 to row 3) and the column sums are $[21, 14, 24]$ (column 1 to column 3).

Given $N$, $M$, a two-dimensional array $A$, and $M$ operations, write a program that computes the row sums and column sums after applying all operations to the array.

The first line contains the number of test cases $T$ ($1 \le T \le 10$).

For each test case, the first line contains two integers $N$ and $M$ separated by a space ($1 \le N \le 1{,}000$, $1 \le M \le 1{,}000$).

The next $N$ lines give the two-dimensional array $A$, where the $i$-th line is the $i$-th row. The $j$-th integer in each line is the value of the element in the $j$-th column. Each element of $A$ is an integer between $1$ and $1{,}000$ inclusive.

The next $M$ lines each contain five integers $r_1, c_1, r_2, c_2, v$ separated by spaces. It always holds that $1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le N$, and $-1{,}000 \le v \le 1{,}000$.

For each test case, print the answer on two lines.

The first line contains the $N$ row sums separated by spaces (row 1 to row $N$).

The second line contains the $N$ column sums separated by spaces (column 1 to column $N$).

The first test case is described in the problem statement.

For the second test case, applying the operation changes the array to the following.

[ [ -20 -10 ]
  [   0  10 ] ].

Thus the row sums are $[-30, 10]$ and the column sums are $[-20, 0]$.

For the third test case, applying all operations leaves a $1 \times 1$ array whose element is 2000.

PyPy is faster than Python in most cases, so if your Python solution exceeds the time limit, it is better to use PyPy.