启程之后

题目描述

橙子反正最后是给了你一个 $n\times n$ 的矩阵，初始全为 $0$，进行 $m$ 次操作，将以 $(x_{1,i},y_{1,i})$ 为左下角、以 $(x_{2,i},y_{2,i})$ 为右上角的子矩阵赋值为 $v_i$，然后 $q$ 次询问，求以 $(a_{1,i},b_{1,i})$ 为左下角、以 $(a_{2,i},b_{2,i})$ 为右上角的子矩阵的值的和。

输入格式

第一行三个整数 $n,m,q$ 表示矩阵大小、操作个数、询问个数。

接下来 $m$ 行，第 $i$ 行五个整数 $x_{1,i},x_{2,i},y_{1,i},y_{2,i},v_i$ 表示一次操作。

接下来 $q$ 行，第 $i$ 行四个整数 $a_{1,i},a_{2,i},b_{1,i},b_{2,i}$ 表示一组询问。

输出格式

对于每组询问，一行一个整数表示答案。

样例 1 输入

3 3 3
1 3 2 3 1
1 2 1 3 3
2 3 2 2 4
1 1 3 3
1 1 2 3
1 3 1 2

样例 1 输出

3
6
17

样例 2 输入

5 5 5
2 5 1 1 7
2 4 1 4 9
3 5 1 3 3
4 5 1 4 5
1 4 1 2 9
1 5 3 5
4 5 3 5
3 5 1 3
2 2 2 3
3 5 4 5

样例 2 输出

50
20
59
18
19

样例 3 输入

10 10 10
2 4 1 8 35
2 7 1 9 67
3 4 1 10 43
4 4 9 9 43
4 5 3 5 89
1 1 8 8 17
2 6 7 8 33
9 9 5 6 7
9 10 2 7 19
6 6 7 8 37
6 10 1 3
2 6 4 10
8 10 5 9
2 7 4 10
2 6 1 3
4 10 7 8
6 10 6 9
3 7 2 4
2 6 4 6
5 6 5 6

样例 3 输出

478
1708
114
2110
929
378
552
997
997
290

样例 4 输入

10 10 1
10 10 3 3 7522451
1 10 3 8 77497312
2 4 8 9 88889398
6 8 1 4 94469398
3 6 2 8 75862961
1 8 4 7 73830116
2 5 3 4 63808705
4 7 6 8 69457181
6 8 6 9 19764004
6 7 2 6 56617770
1 10 1 10

样例 4 输出

4940970884

数据范围

对于所有数据，$1\le n,q\le10^5$，$0\le m\le10^5$，$1\le a_{1,i}\le a_{2,i}\le n$，$1\le b_{1,i}\le b_{2,i}\le n$，$1\le x_{1,i}\le x_{2,i}\le n$，$1\le y_{1,i}\le y_{2,i}\le n$，$1\le v_i\le10^8$。

转换注：原文在本题数据范围及特殊性质中使用 $a_{i,1},a_{i,2}$ 等下标，与题目描述和输入格式中的 $a_{1,i},a_{2,i}$ 写法不同。此处统一采用输入格式的下标顺序，其余变量同理。

子任务

本题采用捆绑测试，并开启所有合理的子任务依赖。

特殊性质 A：对于所有询问，$a_{1,i}=a_{2,i}$，$b_{1,i}=b_{2,i}$。

特殊性质 B：$q=1$，且 $a_{1,i}=b_{1,i}=1$，$a_{2,i}=b_{2,i}=n$。

特殊性质 C：$v_i=i$。