Nuclearia

Long ago the people of Nuclearia built several nuclear plants. The country prospered for many years, then a very strong earthquake hit the land. Every plant exploded and radiation spread across the country. Once the people had stopped any further radiation from escaping, the Ministry of Environment started to measure how polluted the individual regions were. Write a program that answers the queries of the Ministry.

How radiation spreads

Nuclearia is a rectangle of $W \times H$ cells. Each plant occupies one cell and is given by two positive integers. $a$ is the amount of radiation caused to the cell where the plant stood, and $b$ says how fast that radiation drops as you move away from the plant.

The radiation caused to cell $C = [x_C, y_C]$ by the explosion of a plant in cell $P = [x_P, y_P]$ is $\max(0, a - b \cdot d(P, C))$, where $d(P, C) = \max(|x_P - x_C|, |y_P - y_C|)$ is the smallest number of moves a chess king needs between the two cells.

The total radiation in a cell is the sum of the amounts that the individual explosions caused to it.

For example, a plant with $a = 7$ and $b = 3$ causes 7 units of radiation to its own cell, 4 units to the 8 adjacent cells, and 1 unit to the 16 cells at distance 2. If such a plant sits on the border of Nuclearia or one cell away from it, the explosion also reaches cells outside Nuclearia. What happens outside the country is never asked about.

Queries

The Ministry of Environment asks several times about the average radiation per cell in a given rectangular region. The queried regions may overlap or repeat.

The first line contains two space separated positive integers $W$ and $H$, the width and the height of Nuclearia, with $W \cdot H \le 2\,500\,000$.

The second line contains a positive integer $N$, the number of exploded plants ($1 \le N \le 200\,000$).

Each of the next $N$ lines contains four positive integers $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$), describing a plant in cell $[x_i, y_i]$ with parameters $a_i$ and $b_i$. Each cell contains at most one plant.

The next line contains a positive integer $Q$, the number of queries ($1 \le Q \le 200\,000$).

Each of the next $Q$ lines contains four positive integers $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$), describing a query about the rectangle whose upper left corner is cell $[x_{1j}, y_{1j}]$ and whose lower right corner is cell $[x_{2j}, y_{2j}]$.

The total radiation in Nuclearia is less than $2^{63}$.

For each query print one line with the average radiation per cell in the queried region, rounded to the nearest integer. A value that ends in exactly 0.5 is rounded up.

In the first example the radiation in Nuclearia after the two explosions is

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

and the four queries work out as follows.

• The total radiation in the $2 \times 2$ square is 14, so the average is $14/4 = 3.5$, which rounds to 4.
• The total radiation in Nuclearia is 44, so the average is $44/12 \approx 3.67$, which rounds to 4.
• The average over a single cell is the radiation in that cell.
• The average in the last row is $9/4 = 2.25$, which rounds to 2.