题目描述

核能国可以看作一个由 $W \times H$ 的方格组成的矩形。核能国有 $N$ 个核电站，每个核电站占用一个方格。不幸的是，核能国遭遇了百年一遇的特大地震，导致所有的核电站都发生了核泄漏。

每个核电站的核泄漏程度可以用两个整数 $a, b$ 来表示。如果位于 $P=[x_P,y_P]$ 的核电站爆炸，方格 $C=[x_C,y_C]$ 会增加 $\mathrm{max}(0,$ $a-b\times d(P,C))$ 贝克的辐射（贝克是单位），其中 $d(P,C)$ 是两个方格的切比雪夫距离，即 $d(P,C) =$ $\mathrm{max}(|x_P - x_C|,$ $|y_P - y_C|)$。

一个方格可能会受到多处核泄漏的影响。

例如，如果一个 $a = 7,$ $b = 3$ 的核电站爆炸了，所在的方格 $X$ 会受到 $7$ 贝克辐射（贝克是单位），满足 $d(X,Y) = 1$ 的 $8$ 个方格 $Y$ 会受到 $4$ 贝克辐射，满足 $d(X,Z) = 2$ 的 $16$ 个方格 $Z$ 会受到 $1$ 贝克辐射。

环保部门给了你 $Q$ 组询问，每组询问会划定核能国领土中的一个矩形，请回答：矩形区域内（每个方格）所受的平均辐射量为多少。

输入格式

第一行，两个正整数 $W$ 和 $H(W × H \leq 2.5×10^6)$，分别表示核能国的宽度与高度。

第二行，一个正整数 $N$，表示核电站的个数 $(1 \leq N \leq 2×10^5)$。

在接下来的 $N$ 行中，每行四个正整数 $x_i,y_i,a_i,b_i(1 \leq x_i \leq W,1 \leq y_i \leq H,1 \leq a_i,b_i \leq 10^9)$，表示有一个核电站位于方格 $[x_i,y_i]$，它的参数为 $a_i$ 与 $b_I$。每个格子最多有一个核电站。

第 $N+3$ 行，一个正整数 $Q$，表示询问的次数 $(1 \leq Q \leq 2×10^5)$。

在接下来的 $Q$ 行中，每行四个 正整数 $x_{1j},y_{1j},x_{2j},y_{2j}(1 \leq x_{1j} \leq x_{2j} \leq W,1 \leq y_{1j} \leq y_{2j} \leq H)$，表示该询问给出的矩形区域的左上角在 $[x_{1j},y_{1j}]$ 且它的右下角在 $[x_{2j},y_{2j}]$。

你可以假设核能国内的总辐射量少于 $2^{63}$。

输出格式

对于每个询问，输出一行表示给定矩形区域内所有方格的平均辐射量，四舍五入至整数。

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

4
4
2
2

提示

以下为两次爆炸后对每个方格产生的辐射量：

7 6 3 2
4 6 5 2
1 3 3 2

• $2^2$ 方形区域内的总辐射为 $14$，所以平均值为 $14\div 4=3.5$，四舍五入至 $4$。

• 整个核能国的总辐射为 $44$，所以平均值为 $44\div 12 \approx 3.67$，四舍五入至 $4$。

• 单个格子的平均辐射量就是它所受到的辐射量。

• 最后一行的平均辐射量为 $9\div 4=2.25$，四舍五入至 $2$。

有 14 组测试数据。奇数的测试组只包含 $a$ 是 $b$ 的倍数的核电站。对每个子任务的进一步限制如下：

如果核电站位于核能国的边境或是在离边境稍近的位置，那么爆炸可能也会影响到核能国之外的方格。影响到核能国外方格的爆炸被称作界限。