Nuclear Leakage Radiation

The country of Nuclear Energy can be thought of as a \(W \times H\) grid. There are \(N\) nuclear power plants, each occupying a distinct cell. Unfortunately, a massive earthquake triggered nuclear leaks at every plant.

Each plant is characterized by two integers \(a\) and \(b\). When a plant at \(P = [x_P,y_P]\) explodes, every cell \(C = [x_C,y_C]\) receives \(\max(0, a - b \times d(P,C))\) becquerels of radiation, where the Chebyshev distance is defined as \(d(P,C) = \max(|x_P - x_C|, |y_P - y_C|)\). Note that a cell may be affected by the radiation from multiple plants.

For example, if a plant with \(a = 7\) and \(b = 3\) explodes, the cell containing the plant will receive 7 becquerels; each of the 8 surrounding cells (with \(d = 1\)) will receive \(7 - 3 = 4\) becquerels; and the 16 cells at \(d = 2\) will receive \(7 - 6 = 1\) becquerel.

The Environmental Protection Agency has issued \(Q\) queries. Each query specifies a rectangular subregion of the grid, and your task is to compute the average radiation per cell in that rectangle.

inputFormat

The input begins with two integers \(W\) and \(H\) representing the width and height of the grid.

The next integer is \(N\) (the number of nuclear power plants), followed by \(N\) lines. Each of these lines contains four integers: \(x\), \(y\), \(a\), and \(b\). The coordinates \((x, y)\) denote the location of a plant, and \(a\) and \(b\) are its radiation parameters.

Next, an integer \(Q\) is given, representing the number of queries. Each of the following \(Q\) lines contains four integers: \(x_1, y_1, x_2, y_2\). These represent a query rectangle with top-left corner \((x_1, y_1)\) and bottom-right corner \((x_2, y_2)\) (inclusive). It is guaranteed that \(1 \le x_1 \le x_2 \le W\) and \(1 \le y_1 \le y_2 \le H\).

outputFormat

For each query, output one line containing a real number: the average radiation in the specified rectangle. The answer is accepted if it has an absolute or relative error up to \(10^{-6}\).

sample

5 5
1
3 3 7 3
2
3 3 3 3
1 1 5 5

7.000000
2.200000