Grand Escape

SRC (Science Research City) is a city on the first quadrant of the two-dimensional plane. The city has $N$ walls. Each wall is drawn as a line segment parallel to the $x$-axis. Specifically, the $i$-th wall ($1 \leq i \leq N$) is the segment connecting $(Lx_{1,i}, Ly_i)$ and $(Lx_{2,i}, Ly_i)$. Heavy rain that has not stopped raises the risk of flooding, so SRC built shelters along the line $y=0$.

The city has $M$ residents. The $i$-th resident ($1 \leq i \leq M$) is at $(Px_i, Py_i)$. When SRC floods, each resident moves in the $-y$ direction toward $y=0$. The initial speed is $1$.

Every time a resident touches a wall, the speed drops. Touching an endpoint of a segment also counts as touching the wall. If the speed before touching a wall was $\frac{1}{n}$, the speed after touching is $\frac{1}{n+1}$. In other words, the time needed to move 1 unit increases by 1. All $y$-coordinates are distinct. So every resident and every wall has a different $y$-coordinate, and no resident starts on a wall. Multiple $x$-coordinates may be equal.

The first line contains the number of walls $N$.

The next $N$ lines each contain $Lx_{1,i}$, $Lx_{2,i}$, and $Ly_i$, separated by spaces, describing the $i$-th wall. The $i$-th wall is the segment connecting $(Lx_{1,i}, Ly_i)$ and $(Lx_{2,i}, Ly_i)$.

The next line contains the number of residents $M$.

The next $M$ lines each contain the position $Px_i$ and $Py_i$ of the $i$-th resident, separated by a space.

Print $M$ lines. On the $i$-th line, print the time it takes for the $i$-th resident to reach $y=0$.

• $0 \leq N \leq 200,000$ (note that $N=0$ is possible)
• $1 \leq M \leq 200,000$
• $Lx1_i < Lx2_i$
• Every coordinate $(x, y)$ in the input satisfies $1 \leq x, y \leq 10^9$.
• All $y$-coordinates are distinct.
• All numbers in the input are integers.

Some test cases may have answers larger than $2^{31}$, so use the long long type.