P10772 [NOISG 2021 Qualification] Departure

有一个城市，城市里有 $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}$ 天后回家。

#### 数据范围 **本题采用捆绑测试。** 以下定义 $\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$。