很久以前，Nuclearia 的居民决定建造几座核电站。他们繁荣了许多年，但随后遭遇了可怕的不幸。这片土地遭受了极其强烈的地震，导致所有核电站爆炸，辐射开始蔓延到全国。在人们采取了必要措施以防止更多辐射散发后，环境部开始调查各个区域受辐射污染的程度。你的任务是编写一个程序来回答环境部的查询。

辐射如何传播

Nuclearia 可以看作是一个由 $W \times H$ 个单元格组成的矩形。每个核电站占据一个单元格，并由两个正整数参数化：$a$ 表示该核电站所在单元格产生的辐射量，$b$ 表示随着我们远离核电站，产生的辐射量衰减的速度。

更准确地说，位于 $P = [x_P, y_P]$ 的核电站爆炸对单元格 $C = [x_C, y_C]$ 造成的辐射量为 $\max(0, a - b \cdot d(P, C))$，其中 $d(P, C)$ 是两个单元格之间的距离，定义为 $d(P, C) = \max(|x_P - x_C|, |y_P - y_C|)$（即国际象棋中国王在两个单元格之间移动的最少步数）。

一个单元格的总辐射量就是各个爆炸对其造成的辐射量之和。

例如，考虑一个 $a = 7$ 且 $b = 3$ 的核电站。它的爆炸对它所占据的单元格造成 7 单位辐射，对 8 个相邻单元格造成 4 单位辐射，对距离为 2 的 16 个单元格造成 1 单位辐射。注意，如果该核电站位于 Nuclearia 的边缘或距离边缘一个单元格的位置，那么爆炸也会影响 Nuclearia 外部的一些单元格。影响 Nuclearia 外部单元格的爆炸称为边界爆炸（实际上，我们从不关心 Nuclearia 外部发生的事情。我们只需要在下方的评分部分使用这个定义）。

查询

环境部对给定矩形区域内的平均每个单元格的辐射量进行了多次查询。由于环境部内部极其混乱，你无需对查询区域做任何进一步的假设——它们可能会重叠甚至重复。

输入格式

从标准输入读取 Nuclearia 的描述。第一行包含两个空格分隔的正整数 $W$ 和 $H$（其中 $W \cdot H \le 2\,500\,000$），分别代表 Nuclearia 的宽度和高度。第二行包含一个正整数 $N$，即爆炸核电站的数量（$1 \le N \le 200\,000$）。接下来的 $N$ 行，每行包含四个正整数 $x_i, y_i, a_i, b_i$（$1 \le x_i \le W, 1 \le y_i \le H, 1 \le a_i, b_i \le 10^9$），描述了位于单元格 $[x_i, y_i]$ 且参数为 $a_i, b_i$ 的核电站。每个单元格最多包含一个核电站。

下一行包含一个正整数 $Q$，即查询的数量（$1 \le Q \le 200\,000$）。接下来的 $Q$ 行，每行包含四个正整数 $x_{1j}, y_{1j}, x_{2j}, y_{2j}$（$1 \le x_{1j} \le x_{2j} \le W$ 且 $1 \le y_{1j} \le y_{2j} \le H$），描述了一个关于左上角为单元格 $[x_{1j}, y_{1j}]$，右下角为单元格 $[x_{2j}, y_{2j}]$ 的矩形的查询。

你可以假设 Nuclearia 中的总辐射量小于 $2^{63}$。

输出格式

对于每个查询，输出一行，包含查询区域内平均每个单元格的辐射量，四舍五入到最接近的整数（半整数值向上取整）。

样例

输入 1

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

输出 1

4
4
2
2

说明

两次爆炸后 Nuclearia 的辐射情况如下：

$$ \begin{matrix} 7 & 6 & 3 & 2 \\ 4 & 6 & 5 & 2 \\ 1 & 3 & 3 & 2 \end{matrix} $$

注意，第一次爆炸是边界爆炸，而第二次不是。关于查询：

• 2x2 正方形内的总辐射量为 14，因此平均值为 $14/4 = 3.5$，四舍五入为 4。
• Nuclearia 内的总辐射量为 44，因此平均值为 $44/12 \approx 3.67$，四舍五入为 4。
• 单个单元格的平均值就是其中的辐射量。
• 最后一行中的平均辐射量为 $9/4 = 2.25$，四舍五入为 2。

子任务

共有 14 组测试。奇数编号的测试组仅包含 $a$ 是 $b$ 的倍数的核电站。测试组的进一步约束和评分如下：