有一个 $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$。