There are $n$ line segments. The $i$-th line segment connects $(a_i, b_i)$ and $(c_i, d_i)$. These line segments satisfy the following properties:

• For any line segment, $c_i > a_i$ and $d_i < b_i$.
• For any two line segments, they do not share any common points (including endpoints).

There are $Q$ queries. Each query provides a point $(x_i, y_i)$. For each query, calculate the sum of the lengths of the parts of all $n$ line segments that lie within the rectangle with bottom-left corner $(-C, -C)$ and top-right corner $(x_i, y_i)$.

Input

The first line contains a positive integer $n$.

The next $n$ lines each contain four integers $a_i, b_i, c_i, d_i$.

The next line contains a positive integer $Q$.

The next $Q$ lines each contain two integers $x_i, y_i$.

Output

Output $Q$ lines, each containing a non-negative real number representing the answer.

Assuming the sum of the lengths of all input line segments is $S$, your answer is considered correct if and only if for each query, the absolute error between your answer and the standard output does not exceed $10^{-10} \max \{S, 1\}$. In other words, if your output is $a$ and the standard answer is $b$, your answer is considered correct if and only if $|a - b| \le 10^{-10} \max \{S, 1\}$.

Examples

Input 1

3
0 4 2 2
1 4 3 1
2 3 5 0
3
0 0
2 4
3 3

Output 1

0.0000000000
4.6312027626
5.2321279752

Input 2

5
1 2 2 1
0 3 1 1
0 4 2 -1
0 2 1 -5
1 3 5 1
5
-300000 -300000
300000 300000
1 3
2 1
1 2

Output 2

0.0000000000
20.5786501139
10.9226852318
8.2149811903
8.7276182816

Subtasks

• Subtask 1: $n, Q \le 50$ ($8 \%$)
• Subtask 2: $n, Q \le 5000$ ($10 \%$)
• Subtask 3: The sum of the lengths of the line segments does not exceed $10^6$ ($22 \%$)
• Subtask 4: For all line segments, $a_i + b_i = c_i + d_i$ ($15 \%$)
• Subtask 5: No special restrictions ($45 \%$)

For all test data, $C = 3 \times 10^5$, $|a_i|, |b_i|, |c_i|, |d_i|, |x_i|, |y_i| \le 3 \times 10^5$, $n \le 1 \times 10^5$, and $Q \le 1.5 \times 10^5$.