Matrix Range Updates and Maximum Query

You are given an \( n \times n \) matrix \( a \) initially filled with zeros. There will be m modification operations followed by q query operations. First, perform all modification operations and then proceed with the queries.

Modification Operation: Each modification provides five integers \( l_1, l_2, r_1, r_2, x \). For every cell \( a_{i,j} \) where \( l_1 \le i \le r_1 \) and \( l_2 \le j \le r_2 \), add \( x \) to that cell. This can be represented using a difference array as follows:

\[ \begin{aligned} &\text{For each modification:}\\ &a[i][j] += x \quad \text{for } l_1 \le i \le r_1 \text{ and } l_2 \le j \le r_2. \end{aligned} \]

Query Operation: Each query gives four integers \( l_1, l_2, r_1, r_2 \) and asks for the maximum value among all cells \( a_{i,j} \) with \( l_1 \le i \le r_1 \) and \( l_2 \le j \le r_2 \).

Note: The matrix indices are 1-indexed.

inputFormat

The first line contains three integers \( n \), \( m \), and \( q \) representing the size of the matrix, the number of modification operations, and the number of query operations respectively.

The next \( m \) lines each contain five integers \( l_1, l_2, r_1, r_2, x \) representing a modification operation.

The following \( q \) lines each contain four integers \( l_1, l_2, r_1, r_2 \) representing a query operation.

outputFormat

For each query, output a single line containing the maximum value in the specified submatrix after all modifications have been applied.

sample

3 2 2
1 1 2 2 5
2 2 3 3 3
1 1 3 3
2 2 2 2

8
8