Truffles

Near Mirko's village there is a forest where passers-by often find truffles. The forest is a square with side length $2N$ meters. The center of the square is at the origin of the coordinate system, and its sides are parallel to the coordinate axes.

The square is divided into $2N \times 2N$ equal regions, each a square with side length 1 meter. For each region, you know how many grams of truffles someone finds by walking one meter inside that region.

The figure shows the sample.

Mirko plans to take $M$ walks. On each walk, Mirko picks a line that is not parallel to either coordinate axis and walks along that line.

For each walk, print the total number of grams of truffles Mirko finds on that walk. This total is the sum, over every region inside the forest, of the length of the line inside that region multiplied by the region's value. If the line passes through only a single corner point of a region, the length walked in that region is 0.

The first line contains an integer $N$ ($1 \le N \le 500$), half the side length of the forest.

Each of the next $2N$ lines contains $2N$ characters from 1 to 9. Each character is the number of grams of truffles found per meter walked in that region. The regions are listed from north to south (in decreasing order of the $y$ coordinate), and within a line from west to east (in increasing order of the $x$ coordinate), as in the figure above.

The next line contains an integer $M$ ($1 \le M \le 2000$), the number of walks.

Each of the next $M$ lines contains four integers $x_1$, $y_1$, $x_2$, and $y_2$: the coordinates of two different points $(x_1, y_1)$ and $(x_2, y_2)$ on the line Mirko walks along.

It holds that $-10000 \le x_1, y_1, x_2, y_2 \le 10000$, $x_1 \ne x_2$, and $y_1 \ne y_2$.

Print $M$ real numbers, one per line. The $i$-th number is the total number of grams of truffles Mirko finds on the $i$-th walk.

Round each exact value to exactly five digits after the decimal point. If the exact value lies exactly halfway between two candidates, round up. For example, print 0 as 0.00000.