Problem Description

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.

Input Format

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 Format

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.

5 8
0 5
3 11
1 -8
4 10
1 -3
1 2 5 6 8 -3 -7 11

1 5
2 5
1 1
4 3
13 8
4 9
8 9
2 1

3 2
-1 4
-2 5
0 -5
4 -4

6 7
4 5

5 3
0 2
2 4
4 6
6 8
8 10
9 10 10

9 2
5 1
5 1

Hint

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