题目描述
有一个城市,城市里有 N 条路线,每条路线上,在每天午夜会有一辆巴士从起点出发,第二天午夜到达终点。第 i 辆公交车的起点为 Si,终点为 Ei。人们可以在巴士路线上的的任何地方上车、下车或者换乘。
体育馆是这个城市的中心,坐标为 0。在体育馆西边 x 千米的点,坐标为 −x,在体育馆东边 x 千米的点,坐标为 x。
现在有 M 个人需要从体育馆回家,你需要求出每一个人回家的最短时间。
输入格式
第 1 行两个整数 N,M。
第 2 至 N+1 行,每行两个整数 Si,Ei。
第 N+2 行 M 个整数 Pj,表示每一个人的家。
输出格式
M 行,每行两个整数 a,b(gcd(a,b)=1),表示这个人最早能在 ba 天后回家。
提示
数据范围
本题采用捆绑测试。
以下定义 sign(x)=⎩⎨⎧10−1if x>0if x=0if x<0。
Subtask0 为样例。
Subtask1(10 pts)N≤104,M≤103,sign(Si)=sign(Ei)。
Subtask2(14 pts)N≤100,M≤103。
Subtask3(12 pts)N≤103,M≤105,保证最后答案的值均不大于 103,保证任意坐标在不超过 102 条线路上。
Subtask4(8 pts)M≤103,保证任意坐标在不超过 104 条线路上。
Subtask5(15 pts)M≤104,保证最后答案的值均不大于 102。
Subtask6(13 pts)sign(Si)=sign(Ei)。
Subtask7(28 pts)无特殊限制。
数据保证 1≤N,M≤106,−106≤Si,Ei,Pj≤106,Si=Ei,Pj=0。