Ghost

여러분의 팀은 크라쿠프의 바벨 성에 있는 고대 방에 Ghost에 의해 갇혔습니다. Ghost는 질문에 답하기 전까지 여러분을 내보내 주지 않습니다.

벽에는 $n$개의 그림이 걸려 있습니다. 벽을 표준 유클리드 평면으로 보면, 각 그림은 좌표축에 평행한 직사각형입니다. 각 그림의 정확한 크기와 시작 위치를 알고 있습니다. 시각 0에 Ghost가 그림들을 움직이기 시작하며, 각 그림은 저마다 다른 방향과 속력으로 움직입니다. 여러분은 관찰력이 뛰어나서 각 그림의 정확한 속도를 알아낼 수 있습니다.

잠시 후 Ghost가 쇼를 멈추고 까다로운 질문을 던지기 시작합니다. 각 질문은 쇼의 두 시각 $l$과 $r$로 주어집니다. 여러분은 $l$과 $r$ 사이의 어떤 시각에 벽의 한 지점이 모든 그림에 동시에 덮여 있었는지 답해야 합니다. 그랬다면 $l$과 $r$ 사이에서 모든 그림이 겹치는 넓이의 최댓값도 구해야 합니다.

이 방을 나가고 싶다면 Ghost에게 올바른 답을 주십시오.

첫 줄에 테스트 케이스의 수 $z$($1 \le z \le 4000$)가 주어집니다. 각 테스트 케이스는 다음 형식으로 주어집니다.

테스트 케이스의 첫 줄에는 그림의 수 $n$($1 \le n \le 100000$)이 주어집니다. 이어지는 $n$개의 줄에는 여섯 개의 수 $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$)가 주어집니다. 여기서 $(x_1, y_1)$은 그림의 왼쪽 아래 꼭짓점, $(x_2, y_2)$는 오른쪽 위 꼭짓점, $(v_x, v_y)$는 속도 벡터입니다. 시각 $t$에 왼쪽 아래 꼭짓점은 $(x_1 + t v_x, y_1 + t v_y)$에, 오른쪽 위 꼭짓점은 $(x_2 + t v_x, y_2 + t v_y)$에 있습니다.

다음 줄에는 Ghost의 질문 수 $q$($1 \le q \le 100000$)가 주어집니다. 이어지는 $q$개의 줄에는 소수점 아래 최대 4자리까지 주어지는 두 실수 $l$, $r$($0 \le l \le r \le 1000000$)이 주어지며, 이는 닫힌 구간 $[l, r]$을 뜻합니다.

모든 테스트 케이스를 합친 그림의 총수는 1000000을 넘지 않습니다. 모든 테스트 케이스를 합친 질문의 총수도 1000000을 넘지 않습니다.

각 질문마다 구간 $[l, r]$에서 모든 그림의 교집합 넓이의 최댓값을 실수 하나로 한 줄에 출력합니다. 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정합니다. 즉, 출력값을 $a$, 정답을 $b$라 할 때 $|a-b|/\max(1, b) \le 10^{-6}$이면 정답입니다. 교집합이 비어 있으면 0을 출력합니다($\pm 10^{-6}$ 오차 허용).