Near Mirko's village, there is a forest where passersby often find truffles. We can represent the forest as a square with a side length of $2 \cdot N$ meters. The center of the square is at the origin of the coordinate system, and the sides of the square are parallel to the coordinate axes.

The square is divided into $2 \cdot N \times 2 \cdot N$ equal regions, and for each region, it is known how many grams of truffles can be found if we walk one meter through that region.

The image shows a test example

Mirko plans to take $M$ walks. In each walk, Mirko will choose a line that is not parallel to the coordinate axes and walk along that line.

For each walk, output the total number of grams of truffles Mirko can find during that walk.

Input

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

Each of the next $2 \cdot N$ lines contains $2 \cdot N$ characters '1' - '9', representing the number of grams of truffles per meter walked for each region. The regions are listed from north to south (i.e., decreasing in $y$-coordinate) and from west to east (i.e., increasing in $x$-coordinate), as shown in the image 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, y_2$, the coordinates of two distinct points on the line along which Mirko will walk.

Constraints: $-10000 \le x_1, y_1, x_2, y_2 \le 10000$, $x_1 \neq x_2$, $y_1 \neq y_2$.

Output

Output $M$ real numbers with at least 5 decimal places, each on a separate line. The $i$-th of these numbers represents how many grams of truffles Mirko can find in the $i$-th walk.

Examples

Input 1

2 
1357 
2468 
1111 
9999 
4 
0 0 1 1 
-3 0 0 3 
-2 0 2 -1 
2 -4 4 2

Output 1

32.52691 
1.41421 
4.12311 
0.00000