有一个 $n \times n$ 的矩阵 $a$，初始全是 $0$，有 $m$ 次修改操作和 $q$ 次查询操作，先进行所有修改操作，然后进行所有查询操作。

一次修改操作会给出 $l_1,l_2,r_1,r_2,x$，代表把所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $a_{i,j}$ 元素加上一个值 $x$。

一次查询操作会给出 $l_1,l_2,r_1,r_2$，代表查询所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $a_{i,j}$ 元素的最大值。

输入格式

第一行三个由空格分隔的整数 $n,m,q$。

之后 $m$ 行，每行给出五个整数 $l_1,l_2,r_1,r_2,x$，表示一次修改操作。

之后 $q$ 行，每行给出四个整数 $l_1,l_2,r_1,r_2$，表示一次查询操作。

输出格式

输出 $q$ 行，对每次查询操作输出一行一个数表示答案。

样例数据

样例 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

子任务

Idea：apiadu，Solution：ccz181078，Code：apiadu，Data：apiadu&nzhtl1477

注意：本题采用捆绑测试，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

对于其中 $1\%$ 的数据，为样例 1。

对于另外 $9\%$ 的数据，$n=1$。

对于另外 $19\%$ 的数据，$n,m\leq 500$。

对于另外 $19\%$ 的数据，$n\leq 2000$，$q\leq 2\times 10^5$。

对于另外 $19\%$ 的数据，$m,q\leq 2000$。

对于 $100\%$ 的数据，$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$。