2차원 배열 범위 덧셈과 구간 합

크기가 $n \times n$인 정수형 2차원 배열 $A$가 주어진다. 배열의 원소는 $A[0][0], A[0][1], \ldots, A[n-1][n-1]$이다. 모든 원소의 초깃값은 입력으로 주어진다. 배열 $B$에는 $A$에 대한 $m$개의 질의가 저장되어 있으며, 질의는 아래 두 가지 유형 중 하나이다. 첫 번째 유형은 유형 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$에는 모든 유형 1의 질의가 유형 2의 질의보다 앞부분에 저장되어 있다.

첫 번째 줄에 $n$과 $m$이 공백을 사이에 두고 주어진다. 다음 $n$개의 줄에는 배열 $A$의 원소가 주어진다. $i$번째 줄의 $j$번째 수는 $A[i-1][j-1]$이다. 그다음 $m$개의 줄에 질의가 한 줄에 하나씩 순서대로 주어진다. 각 줄의 수는 공백으로 구분된다.

유형 2 질의의 결과를 순서대로 한 줄에 하나씩 출력한다.

• $1 \le n \le 1000$, $1 \le m \le 300000$
• $1 \le A[i][j] \le 1000000$ ($0 \le i, j \le n-1$)
• 배열 $B$에는 유형 1과 유형 2의 질의만 존재한다.
• 배열 $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 10000$