题目描述

有一个城市，城市里有 $N$ 条路线，每条路线上，在每天午夜会有一辆巴士从起点出发，第二天午夜到达终点。第 $i$ 辆公交车的起点为 $S_i$，终点为 $E_i$。人们可以在巴士路线上的的任何地方上车、下车或者换乘。

体育馆是这个城市的中心，坐标为 $0$。在体育馆西边 $x$ 千米的点，坐标为 $-x$，在体育馆东边 $x$ 千米的点，坐标为 $x$。

现在有 $M$ 个人需要从体育馆回家，你需要求出每一个人回家的最短时间。

输入格式

第 $1$ 行两个整数 $N,M$。

第 $2$ 至 $N+1$ 行，每行两个整数 $S_i,E_i$。

第 $N+2$ 行 $M$ 个整数 $P_j$，表示每一个人的家。

输出格式

$M$ 行，每行两个整数 $a,b$（$\gcd(a,b)=1$），表示这个人最早能在 $\dfrac{a}{b}$ 天后回家。

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

提示

数据范围

本题采用捆绑测试。

以下定义 $\operatorname{sign}(x) = \begin{cases} 1 &\text{if } x > 0 \\ 0 &\text{if } x = 0 \\ -1 &\text{if } x < 0 \\ \end{cases}$。

Subtask0 为样例。

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$，保证最后答案的值均不大于 $10^3$，保证任意坐标在不超过 $10^2$ 条线路上。

Subtask4（8 pts）$M \leq 10^3$，保证任意坐标在不超过 $10^4$ 条线路上。

Subtask5（15 pts）$M \leq 10^4$，保证最后答案的值均不大于 $10^2$。

Subtask6（13 pts）$\operatorname{sign}(S_i)\neq\operatorname{sign}(E_i)$。

Subtask7（28 pts）无特殊限制。

数据保证 $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$。