在学习了 KD-tree 之后，你想出了以下问题。这对该数据结构来说应该是一个很好的测验。

你被给定一个 $n \times n$ 的矩阵 $A$。所有元素初始均为零。

首先，你需要执行 $m_1$ 次区间加法操作。对于每次操作，给定 $x_1, y_1, x_2, y_2, w$ ($1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le n$)。你需要将所有满足 $x_1 \le i \le x_2$ 且 $y_1 \le j \le y_2$ 的元素 $A_{i,j}$ 加上 $w$。

然后，你需要执行 $m_2$ 次区间最大值查询。对于每次操作，给定 $x_1, y_1, x_2, y_2$ ($1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le n$)。你需要找出满足 $x_1 \le i \le x_2$ 且 $y_1 \le j \le y_2$ 的元素 $A_{i,j}$ 中的最大值。

输入格式

第一行包含三个整数 $n, m_1, m_2$ ($1 \le n \le 5 \cdot 10^4, 1 \le m_1 \le 5 \cdot 10^4, 1 \le m_2 \le 5 \cdot 10^5$)。

接下来的 $m_1$ 行，每行包含五个整数 $x_1, y_1, x_2, y_2, w$ ($1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le n, 1 \le w \le 10^9$)。

接下来的 $m_2$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$ ($1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le n$)。

输出格式

输出 $m_2$ 行，每行包含一个整数，表示对应查询的答案。

样例

输入 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