Background

Uh...

This problem has an input size of about 13 MB and an output size of about 7 MB. Please choose an appropriate input/output method.

Problem Description

There is an $n \times n$ matrix $a$, initially all $0$. There are $m$ update operations and $q$ query operations. All update operations are performed first, and then all query operations are performed.

An update operation gives $l_1,l_2,r_1,r_2,x$, meaning to add a value $x$ to all elements $a_{i,j}$ satisfying $l_1 \le i \le r_1$ and $l_2 \le j \le r_2$.

A query operation gives $l_1,l_2,r_1,r_2$, meaning to query the maximum value among all elements $a_{i,j}$ satisfying $l_1 \le i \le r_1$ and $l_2 \le j \le r_2$.

Input Format

The first line contains three integers $n,m,q$ separated by spaces.

The next $m$ lines each contain five integers $l_1,l_2,r_1,r_2,x$, describing an update operation.

The next $q$ lines each contain four integers $l_1,l_2,r_1,r_2$, describing a query operation.

Output Format

Output $q$ lines. For each query operation, output one number per line as the answer.

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

12
22
20
22
20

Hint

Idea: apiadu, Solution: ccz181078, Code: apiadu, Data: apiadu & nzhtl1477.

Note: This problem uses bundled subtasks. You can only get the score for a subtask after passing all test points in that subtask.

For $1\%$ of the testdata, it is Sample 1.

For another $9\%$ of the testdata, $n=1$.

For another $19\%$ of the testdata, $n,m\leq 500$.

For another $19\%$ of the testdata, $n\leq 2000$ and $q\leq 2\times 10^5$.

For another $19\%$ of the testdata, $m,q\leq 2000$.

Constraints: For $100\%$ of the testdata, $1\leq n,m\leq 5\times 10^4$, $1\leq q \leq 5\times 10^5$, $1\leq x\leq 2147483647$, $1\leq l_1\leq r_1\leq n$, $1\leq l_2\leq r_2\leq n$.

Translated by ChatGPT 5