Problem Description

In a city, there are $N$ routes. On each route, a bus departs from the starting point at midnight and arrives at the destination the next midnight. The $i$-th bus starts at $S_i$ and ends at $E_i$. People can board, alight, or transfer at any point along the bus routes.

The gym is the center of the city, located at coordinate $0$. A point $x$ kilometers west of the gym has a coordinate of $-x$, and a point $x$ kilometers east of the gym has a coordinate of $x$.

There are $M$ people who need to return home from the gym, and you need to determine the shortest time for each person to get home.

Input Format

The first line contains two integers $N$ and $M$.

The next $N$ lines contain two integers each, $S_i$ and $E_i$.

The $(N+2)$-th line contains $M$ integers $P_j$, representing the homes of each person.

Output Format

$M$ lines, each containing two integers $a$ and $b$ ($\gcd(a,b)=1$), indicating that the person can return home earliest in $\dfrac{a}{b}$ days.

Sample Input and Output

Sample Input #1

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

Sample Output #1

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

Sample Input #2

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

Sample Output #2

6 7
4 5

Sample Input #3

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

Sample Output #3

9 2
5 1
5 1

Notes

Data Range

This problem uses batched testing.

Define $\operatorname{sign}(x) = \begin{cases}
1 &$\text{if$ } x > 0 \
0 &$\text{if$ } x = 0 \
-1 &$\text{if$ } x < 0 \
\end{cases}$.

Subtask0 is the sample.

Subtask1 (10 pts) $N \leq 10^4$, $M \leq 10^3$, $\operatorname{sign}(S_i)\neq\operatorname{sign}(E_i)$.

Subtask2 (14 pts) $N \leq 100$, $M \leq 10^3$.

Subtask3 (12 pts) $N \leq 10^3$, $M \leq 10^5$, guaranteed that the final answers are all no greater than $10^3$, and any coordinate is on no more than $10^2$ routes.

Subtask4 (8 pts) $M \leq 10^3$, guaranteed that any coordinate is on no more than $10^4$ routes.

Subtask5 (15 pts) $M \leq 10^4$, guaranteed that the final answers are all no greater than $10^2$.

Subtask6 (13 pts) $\operatorname{sign}(S_i)\neq\operatorname{sign}(E_i)$.

Subtask7 (28 pts) No special restrictions.

Data guarantees $1 \leq N,M \leq 10^6$, $-10^6 \leq S_i,E_i,P_j \leq 10^6$, $S_i \neq E_i$, $P_j \neq 0$.

见题面 Input 部分

见题面 Output 部分