직사각형 갱신과 구간 합

시간 제한1초메모리 제한256 MB

요약

업데이트마다 사각형 안 모든 칸에 w를 더하고 조회마다 사각형 안 칸 합을 순서대로 출력합니다.

난이도: 보통10점 중 7점
유형: 세그먼트 트리, 누적 합, 행렬
정답자: 아직 제출이 없습니다

문제

$N \times M$ 크기의 격자가 있다. 행은 아래에서 위로 1번부터 $N$ 번까지, 열은 왼쪽에서 오른쪽으로 1번부터 $M$ 번까지 번호가 붙어 있고, 처음에는 모든 칸의 값이 0이다. 칸 $(i, j)$ 는 $i$ 번 행과 $j$ 번 열이 만나는 자리를 뜻한다.

격자에 다음 두 가지 연산을 주어진 순서대로 $Q$ 번 수행한다.

1 a b x y w: 왼쪽 아래 칸이 $(a, b)$ 이고 오른쪽 위 칸이 $(x, y)$ 인 직사각형에 속한 모든 칸에 $w$ 를 더한다.

2 a b x y: 왼쪽 아래 칸이 $(a, b)$ 이고 오른쪽 위 칸이 $(x, y)$ 인 직사각형에 속한 모든 칸의 값을 더한 결과를 출력한다.

입력

첫째 줄에 $N$ , $M$ , $Q$ 가 공백으로 구분되어 주어진다. 다음 $Q$ 개의 줄에는 위에서 정한 형식의 연산이 한 줄에 하나씩 주어진다.

$1 \le N, M \le 1000$ 이고 $1 \le Q \le 100000$ 이다. 모든 연산은 $1 \le a \le x \le N$ , $1 \le b \le y \le M$ 을 만족하며, 1번 연산의 $w$ 는 $1 \le w \le 1000$ 인 정수이다.

출력

2번 연산마다 계산한 합을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다. 합은 32비트 정수 범위를 넘을 수 있다.

예제7

예제 1

입력

2 3 8
1 1 1 1 1 5
1 1 1 1 2 5
2 1 2 1 3
1 1 1 2 1 4
2 2 1 2 2
2 1 2 1 3
1 2 1 2 2 5
2 1 1 1 1

예상 출력

예제 2

입력

1 1 5
2 1 1 1 1
1 1 1 1 1 7
2 1 1 1 1
1 1 1 1 1 1000
2 1 1 1 1

예상 출력

0
7
1007

예제 3

입력

4 5 6
2 1 1 4 5
1 2 2 3 4 3
2 1 1 4 5
2 2 2 3 4
2 1 1 1 1
2 3 4 4 5

예상 출력

예제 4

입력

3 3 9
1 1 1 3 3 1
1 2 2 3 3 2
1 3 3 3 3 4
2 1 1 3 3
2 2 2 3 3
2 3 3 3 3
1 1 1 1 3 10
2 1 1 1 3
2 1 1 3 3

예상 출력

예제 5

입력

1 10 8
1 1 1 1 10 2
2 1 1 1 10
1 1 3 1 7 5
2 1 3 1 7
2 1 1 1 2
1 1 5 1 5 100
2 1 5 1 5
2 1 1 1 10

예상 출력

예제 6

입력

10 1 8
1 1 1 10 1 2
2 1 1 10 1
1 3 1 7 1 5
2 3 1 7 1
2 1 1 2 1
1 5 1 5 1 100
2 5 1 5 1
2 1 1 10 1

예상 출력

예제 7

입력

5 5 7
1 1 1 5 5 4
1 2 3 4 4 6
2 1 1 5 5
2 1 1 2 5
2 3 1 5 5
2 1 1 5 2
2 1 3 5 5

예상 출력