Ghost

Your team has been trapped in an ancient chamber at Wawel Castle in Kraków by the Ghost. He will not let you out unless you answer his questions.

On the wall there are $n$ paintings. If we treat the wall as the standard Euclidean plane, each painting is an axis-aligned rectangle. For every painting you know its exact dimensions and starting position. At moment 0, the Ghost starts moving the paintings, each one in its own direction and speed. You are an observant team, so you can work out the exact speed of every painting.

After some time, the Ghost stops the show and starts asking tough questions. Each question gives two numbers $l$ and $r$, which are moments of the show. You must tell the Ghost whether there was a moment between $l$ and $r$ when some spot on the wall was covered by all the paintings at once. If so, you must also find the maximum possible common area of all paintings between moments $l$ and $r$.

If you ever want to leave this room, give the Ghost the right answers.

The first line contains the number of test cases $z$ ($1 \le z \le 4000$). Each test case has the following format.

The first line of a test case contains the number of paintings $n$ ($1 \le n \le 100000$). Each of the next $n$ lines contains six numbers $x_1, y_1, x_2, y_2, v_x, v_y$ ($-1000000 \le x_1 < x_2 \le 1000000$; $-1000000 \le y_1 < y_2 \le 1000000$; $-1000000 \le v_x, v_y \le 1000000$), where $(x_1, y_1)$ is the lower left corner of the painting, $(x_2, y_2)$ is its upper right corner, and $(v_x, v_y)$ is its speed vector. At moment $t$, the lower left corner is at $(x_1 + t v_x, y_1 + t v_y)$ and the upper right corner is at $(x_2 + t v_x, y_2 + t v_y)$.

The next line contains the number of Ghost's questions $q$ ($1 \le q \le 100000$). Each of the next $q$ lines contains two real numbers $l$ and $r$ ($0 \le l \le r \le 1000000$) with at most 4 decimal places, which denote the closed time interval $[l, r]$.

The total number of paintings across all test cases does not exceed 1000000. The total number of questions across all test cases does not exceed 1000000.

For each question, print one real number: the maximum area of the intersection of all paintings during the interval $[l, r]$. Your answer is accepted if the absolute or relative error is at most $10^{-6}$. That is, if your output is $a$ and the correct value is $b$, it is accepted when $|a-b|/\max(1, b) \le 10^{-6}$. If the intersection is empty, print 0 (an error of $\pm 10^{-6}$ is allowed).