시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 512 MB 100 50 8 29.630%

문제

After learning KD-tree, you came up with the following problem. It should be a great quiz for this data structure.

You are given an n × n matrix A. All elements are zero initially.

First, you need to perform m1 range addition operations. For each operation, you are given x1, y1, x2, y2, w (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n). You need to add w to all the elements Ai,j where x1 ≤ i ≤ x2 and y1 ≤ j ≤ y2.

Then you need to perform m2 range maximum queries. For each operation, you are given x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n). You need to find the maximum element among the elements Ai,j that satisify x1 ≤ i ≤ x2 and y1 ≤ j ≤ y2.

입력

The first line contains three integers n, m1, m2 (1 ≤ n ≤ 5 · 104, 1 ≤ m1 ≤ 5 · 104, 1 ≤ m2 ≤ 5 · 105).

Each of the following m1 lines contains five integers x1, y1, x2, y2, w (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n, 1 ≤ w ≤ 109).

Each of the following m2 lines contains four integers x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n).

출력

Output m2 lines, each line containing one integer: the answer to the respective query.

예제 입력 1

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

예제 출력 1

12
22
20
22
20