Grand Escape

SRC(Science Research City)는 2차원 평면, 그중에서도 제1사분면에 있는 도시이다. 도시에는 $N$개의 벽이 있다. 벽은 $x$축과 평행한 선분으로 표현된다. 구체적으로 $i$($1 \leq i \leq N$)번째 벽은 $(Lx_{1,i}, Ly_i)$와 $(Lx_{2,i}, Ly_i)$를 잇는 선분이다. 그치지 않는 비로 침수 위험이 커지자, SRC는 직선 $y=0$을 따라 대피소를 지었다.

도시에는 $M$명의 사람이 산다. $i$($1 \leq i \leq M$)번째 사람은 $(Px_i, Py_i)$ 위치에 있다. SRC에 홍수가 나면 각 사람은 $y=0$을 향해 $-y$ 방향으로 이동한다. 초기 속도는 $1$이다.

사람은 벽에 닿을 때마다 속도가 줄어든다. 선분의 끝점에 닿는 것도 벽에 닿는 것으로 본다. 벽에 닿기 전 속도가 $\frac{1}{n}$이었다면, 닿은 뒤의 속도는 $\frac{1}{n+1}$이 된다. 즉 $1$칸을 이동하는 데 걸리는 시간이 $1$만큼 늘어난다. 모든 $y$좌표는 서로 겹치지 않는다. 따라서 사람과 벽의 $y$좌표는 모두 다르며, 사람의 초기 위치가 벽과 겹치는 일은 없다. $x$좌표는 같을 수 있다.

첫 번째 줄에 벽의 수 $N$이 주어진다.

이후 $N$개의 줄에 걸쳐 $i$번째 줄에 $i$번째 벽의 정보인 $Lx_{1,i}$, $Lx_{2,i}$, $Ly_i$가 공백으로 구분되어 주어진다. $i$번째 벽은 $(Lx_{1,i}, Ly_i)$와 $(Lx_{2,i}, Ly_i)$를 잇는 선분이다.

다음 줄에 사람의 수 $M$이 주어진다.

이후 $M$개의 줄에 걸쳐 $i$번째 줄에 $i$번째 사람의 위치 $Px_i$, $Py_i$가 공백으로 구분되어 주어진다.

$M$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 사람이 $y=0$에 도달하는 데 걸리는 시간을 출력한다.

• $0 \leq N \leq 200,000$ ($N=0$일 수 있음에 주의하라)
• $1 \leq M \leq 200,000$
• $Lx1_i < Lx2_i$
• 입력에서 주어지는 모든 좌표 $(x, y)$는 $1 \leq x, y \leq 10^9$를 만족한다.
• 모든 $y$좌표는 서로 겹치지 않는다.
• 입력에서 주어지는 모든 수는 정수이다.

이 문제의 일부 테스트 케이스는 답이 $2^{31}$을 넘어갈 수 있으므로 long long 자료형을 쓰도록 하자.