[CEOI2015Day2] Nuclearia

内存限制：1024 MB 时间限制：1000 ms

Long ago, the people of Nuclearia decided to build several nuclear plants. They prospered for many years, but then a terrible misfortune befell them. The land was hit by an extremely strong earthquake, which caused all the nuclear plants to explode, and radiation began to spread throughout the country. When the people had made necessary steps so that no more radiation would emanate, the Ministry of Environment started to ﬁnd out how much individual regions were polluted by the radiation. Your task is to write a program that will answer the queries of the Ministry.

How radiation spreads

Nuclearia can be viewed as a rectangle consisting of $W × H$ cells. Each nuclear plant occupies one cell and is parametrized by two positive integers: $a$, which is the amount of radiation caused to the cell where the plant was, and $b$, which describes how rapidly the caused radiation decreases as we go farther from the plant.

More precisely, the amount of radiation caused to cell $C = [x_C,y_C]$ by explosion of a plant in cell $P = [x_P,y_P]$ is $\max(0,a−b\cdot d(P,C))$, where $d(P,C)$ is the distance of the two cells, deﬁned by $d(P,C) = \max(|x_P −x_C|,|y_P −y_C|)$ (i.e., the minimum number of moves a chess king would travel between them).

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

As an example, consider a plant with $a = 7$ and $b = 3$. Its explosion causes $7$ units of radiation to the cell it occupies, $4$ units of radiation to the $8$ adjacent cells, and $1$ unit of radiation to the $16$ cells whose distance is $2$. Note that if this plant is situated on the edge of Nuclearia or one cell away from the edge, then the explosion also aﬀects some cells outside Nuclearia. An explosion that aﬀects cells outside Nuclearia is called boundary. (Actually, we are never interested in what happens outside Nuclearia. We just need this deﬁnition in the Grading section below.)

Queries

The Ministry of Environment makes several queries about the average-per-cell radiation in a given rectangular region. As great chaos rules in the Ministry, you may make no further assumptions about the queried regions — they may overlap or even repeat.

The description of Nuclearia is read from the standard input. The ﬁrst line contains two space-separated positive integers $W$ and $H$ (where $W·H ≤ 2500000$) which stand for the width and height of Nuclearia, respectively. The second line contains a positive integer $N$, which is the number of exploded plants $(1 ≤ N ≤ 200000)$. Each of the following $N$ lines contains four positive integers $x_i,y_i,a_i,b_i (1 ≤ x_i ≤ W, 1 ≤ y_i ≤ H, 1 ≤ a_i,b_i ≤ 10^9)$, which describe a plant in cell $[x_i,y_i]$ with parameters $a_i,b_i$. Each cell contains at most one plant.

The following line contains a positive integer $Q$, which is the number of queries $(1 ≤ Q ≤ 200000)$. Each of the following $Q$ lines contains four positive integers $x_{1j},y_{1j},x_{2j},y_{2j} (1 ≤ x_{1j} ≤ x_{2j} ≤ W$ and $1 ≤ y_{1j} ≤ y_{2j} ≤ H)$, which describe a query about the rectangle whose upper-left corner is the cell $[x_{1j},y_{1j}]$ and lower-right corner is the cell $[x_{2j},y_{2j}]$.

You can assume that the total radiation in Nuclearia is less than $2^{63}$.

For each query, output a line which contains the average-per-cell radiation in the queried region, rounded to the nearest integer (half-integral values are rounded up).

样例输入 1

样例输出 1

There are 14 groups of tests. The groups of tests with odd numbers only contain plants for which a is $a$ multiple of $b$. Further constraints on groups of tests and their grading are as follows.

C1721 [CEOI2015Day2] Nuclearia

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示