2차원 배열 다중 업데이트 단일 합

크기가 $n \times n$인 정수형 2차원 배열 $A$가 주어진다. 배열 $A$의 원소는 $A[0][0], A[0][1], \ldots, A[n-1][n-1]$이다. 배열 $A$의 모든 원소의 초깃값은 입력으로 주어진다. 배열 $A$에 대한 $m$개의 질의가 담긴 배열 $B$가 주어진다. 배열 $B$의 질의는 다음 두 유형 중 하나이며, 유형 1이 먼저, 유형 2가 나중에 나온다.

• 1 $i_1$ $j_1$ $i_2$ $j_2$ $k$: $i_1 \le i \le i_2$이고 $j_1 \le j \le j_2$인 $A[i][j]$마다 $k$를 더한다.
• 2 $i_1$ $j_1$ $i_2$ $j_2$: $i_1 \le i \le i_2$이고 $j_1 \le j \le j_2$인 $A[i][j]$의 합을 출력한다.

배열 $B$의 첫 번째 질의부터 $m$번째 질의까지 순서대로 처리하면서 유형 2 질의의 결과를 출력하자. 단, 배열 $B$에는 유형 2의 질의가 마지막에 1개만 저장되어 있다.

첫 번째 줄에 $n$과 $m$이 공백을 사이에 두고 주어진다.

두 번째 줄부터 $n$개의 줄에 배열 $A$의 원소가 주어진다. $i$번째 줄의 $j$번째 수는 $A[i-1][j-1]$이다.

다음 줄부터 $m$개의 줄에 배열 $B$의 질의가 순서대로 주어진다. 한 줄에 질의 하나가 공백으로 구분된 수들로 주어진다.

첫 번째 줄에 유형 2 질의의 결과를 출력한다.

• $1 \le n \le 1{,}000$, $1 \le m \le 300{,}000$
• $1 \le A[i][j] \le 1{,}000{,}000$ ($0 \le i, j \le n-1$)
• 배열 $B$의 질의는 유형 1과 유형 2뿐이다.
• 배열 $B$에는 유형 2의 질의가 마지막에 1개만 있다.
• $0 \le i_1 \le i_2 \le n-1$
• $0 \le j_1 \le j_2 \le n-1$
• $1 \le k \le 10{,}000$