31743번 - 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$좌표는 같을 수 있음에 유의하라.

당신은 $M$명의 사람 각각에 대해 $y=0$에 도달하기 위해 걸리는 시간을 구해야 한다.

입력

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

이후 $N$줄에 걸쳐 그중 $i(1\leq i\leq N)$번째 줄에 $i$번째 벽에 대한 정보 $Lx_{1,i}, Lx_{2,i}, Ly_i$가 공백으로 구분되어 주어진다. $i$번째 벽은 $(Lx_{1,i},Ly_i) ,(Lx_{2,i},Ly_i)$을 잇는 선분이라는 의미이다.

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

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

출력

$M$개의 줄을 출력한다. $i(1\leq i\leq M)$번째 줄에 $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 자료형을 쓰도록 하자.