배열 놀이

$N$개의 행과 $N$개의 열로 이루어진 2차원 정수 배열 $A$가 있다. $A[r, c]$는 $r$번째 행 $c$번째 열에 있는 원소의 값을 나타낸다.

이 배열에 총 $M$번의 연산을 적용하는 배열 놀이를 생각해보자.

각 연산은 $1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le N$, $-1{,}000 \le v \le 1{,}000$을 만족하는 다섯 개의 정수 $(r_1, c_1, r_2, c_2, v)$로 주어지며, $(r_1, c_1)$부터 $(r_2, c_2)$까지의 사각형 영역에 속한 $A[r, c]$의 값에 $v$를 더한다.

예를 들어 $N = 3$이고 $A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]$인 배열에 다음 세 개의 연산을 순서대로 적용한다고 하자.

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

연산을 적용하기 전 $A$는 다음과 같다.

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

연산 1을 적용하면 첫 두 행에 포함된 여섯 개의 원소 값이 바뀌어 다음과 같아진다.

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

연산 2를 적용한 후:

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

연산 3을 적용한 후:

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

이렇게 세 개의 연산을 모두 적용한 다음, 마지막으로 얻은 배열의 각 행 원소 합과 각 열 원소 합을 구하려고 한다. 위 예에서 행 원소 합은 $[17, 21, 21]$이고(1번 행부터 3번 행까지), 열 원소 합은 $[21, 14, 24]$이다(1번 열부터 3번 열까지).

$N$, $M$, 2차원 배열 $A$, $M$개의 연산이 주어졌을 때, 배열에 연산을 모두 적용한 후 각 행 원소 합과 각 열 원소 합을 구하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 10$).

각 테스트 케이스는 다음과 같다. 첫 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다 ($1 \le N \le 1{,}000$, $1 \le M \le 1{,}000$).

다음 $N$줄에 걸쳐 2차원 배열 $A$가 주어지며, $i$번째 줄이 $i$번째 행을 나타낸다. 각 줄의 $j$번째 정수는 $j$번째 열의 원소 값을 나타낸다. 배열 $A$의 각 원소는 $1$ 이상 $1{,}000$ 이하의 정수이다.

다음 $M$줄에 걸쳐 각 줄에 다섯 개의 정수 $r_1, c_1, r_2, c_2, v$가 공백으로 구분되어 주어진다. 항상 $1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le N$, $-1{,}000 \le v \le 1{,}000$을 만족한다.

각 테스트 케이스마다 두 줄에 걸쳐 정답을 출력한다.

첫째 줄에는 $N$개의 정수로 표현된 각 행의 합을 공백으로 구분하여 출력한다(1번 행부터 $N$번 행까지).

둘째 줄에는 $N$개의 정수로 표현된 각 열의 합을 공백으로 구분하여 출력한다(1번 열부터 $N$번 열까지).

첫 번째 테스트 케이스는 문제에 설명되어 있다.

두 번째 테스트 케이스에서 연산을 적용하면 배열이 다음과 같이 바뀐다.

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

따라서 행 원소 합은 $[-30, 10]$이고 열 원소 합은 $[-20, 0]$이다.

세 번째 테스트 케이스에서 연산을 모두 적용하면 원소 값이 2000인 $1 \times 1$ 배열이 남는다.

대부분의 경우 PyPy가 Python보다 빠르므로, Python으로 시간 초과를 받으면 PyPy를 사용하는 것이 좋다.