18756번 - Data Structure Quiz 다국어

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 m₁ range addition operations. For each operation, you are given x₁, y₁, x₂, y₂, w (1 ≤ x₁ ≤ x₂ ≤ n, 1 ≤ y₁ ≤ y₂ ≤ n). You need to add w to all the elements A_i,j where x₁ ≤ i ≤ x₂ and y₁ ≤ j ≤ y₂.

Then you need to perform m₂ range maximum queries. For each operation, you are given x₁, y₁, x₂, y₂ (1 ≤ x₁ ≤ x₂ ≤ n, 1 ≤ y₁ ≤ y₂ ≤ n). You need to find the maximum element among the elements A_i,j that satisify x₁ ≤ i ≤ x₂ and y₁ ≤ j ≤ y₂.

The first line contains three integers n, m₁, m₂ (1 ≤ n ≤ 5 · 10⁴, 1 ≤ m₁ ≤ 5 · 10⁴, 1 ≤ m₂ ≤ 5 · 10⁵).

Each of the following m1 lines contains five integers x₁, y₁, x₂, y₂, w (1 ≤ x₁ ≤ x₂ ≤ n, 1 ≤ y₁ ≤ y₂ ≤ n, 1 ≤ w ≤ 10⁹).

Each of the following m2 lines contains four integers x₁, y₁, x₂, y₂ (1 ≤ x₁ ≤ x₂ ≤ n, 1 ≤ y₁ ≤ y₂ ≤ n).

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