There are $n$ line segments on a plane.

There are $m$ queries. Each query provides a rectangle with sides parallel to the coordinate axes. For each query, calculate the ratio of the sum of the lengths of the intersections between each line segment and the rectangle to the sum of the lengths of all line segments. The output must have a relative or absolute error not exceeding $10^{-6}$.

Line segments are given as $x_1\;y_1\;x_2\;y_2$, representing a segment with endpoints $(x_1, y_1)$ and $(x_2, y_2)$. It is guaranteed that no two line segments intersect or overlap, and $x_1 \neq x_2, y_1 \neq y_2$.

Rectangles are given as $x_1\;y_1\;x_2\;y_2$, representing the rectangle $\{(x, y) | x_1 \le x \le x_2, y_1 \le y \le y_2\}$. It is guaranteed that $x_1 < x_2$ and $y_1 < y_2$.

Input

The first line contains an integer $n$.

The next $n$ lines each contain four space-separated integers $x_1, y_1, x_2, y_2$, representing the line segments.

The next line contains an integer $m$.

The next $m$ lines each contain four space-separated integers $x_1, y_1, x_2, y_2$, representing the query rectangles.

Output

For each query, output a single line containing a decimal number between $0$ and $1$, representing the answer.

Examples

Input 1

2
1 1 4 4
2 1 4 3
4
1 1 6 6
1 1 3 3
2 1 3 3
1 2 2 4

Output 1

1
0.6
0.4
0

Subtasks

Idea: nzhtl1477 & ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

For $100\%$ of the data, $1 \le n, m \le 10^5$, $1 \le x_1, y_1, x_2, y_2 \le 10^6$.