P10772 [NOISG 2021 Qualification] Departure

There is a city with $N$ routes. On each route, every day at midnight, a bus departs from the starting point and arrives at the destination at midnight of the next day. The start of the $i$-th bus is $S_i$, and the end is $E_i$. People can board, get off, or transfer at **any position** along a bus route. The stadium is the center of this city, with coordinate $0$. A point $x$ kilometers to the west of the stadium has coordinate $-x$, and a point $x$ kilometers to the east has coordinate $x$. Now there are $M$ people who need to go home from the stadium. You need to find the shortest time for each person to get home.

The first line contains two integers $N, M$. Lines $2$ to $N + 1$ each contain two integers $S_i, E_i$. Line $N + 2$ contains $M$ integers $P_j$, representing each person's home.

Output $M$ lines. Each line contains two integers $a, b$ ($\gcd(a,b)=1$), meaning that this person can get home at the earliest after $\dfrac{a}{b}$ days.

#### Constraints **This problem uses bundled testdata.** Define $\operatorname{sign}(x) = \begin{cases} 1 &\text{if } x > 0 \\ 0 &\text{if } x = 0 \\ -1 &\text{if } x < 0 \\ \end{cases}$. Subtask 0 is the sample. Subtask 1 (10 pts): $N \leq 10^4$, $M \leq 10^3$, $\operatorname{sign}(S_i)\neq\operatorname{sign}(E_i)$. Subtask 2 (14 pts): $N \leq 100$, $M \leq 10^3$. Subtask 3 (12 pts): $N \leq 10^3$, $M \leq 10^5$, it is guaranteed that the final answer values are all no more than $10^3$, and any coordinate lies on no more than $10^2$ routes. Subtask 4 (8 pts): $M \leq 10^3$, it is guaranteed that any coordinate lies on no more than $10^4$ routes. Subtask 5 (15 pts): $M \leq 10^4$, it is guaranteed that the final answer values are all no more than $10^2$. Subtask 6 (13 pts): $\operatorname{sign}(S_i)\neq\operatorname{sign}(E_i)$. Subtask 7 (28 pts): no special constraints. It is guaranteed that $1 \leq N, M \leq 10^6$, $-10^6 \leq S_i,E_i,P_j \leq 10^6$, $S_i \neq E_i$, and $P_j \neq 0$. Translated by ChatGPT 5