[Croatian CPC2016] Rudar
题目描述
矿洞的地面是一条由 n+1 个顶点 (x0,y0),(x1,y1),…,(xn,yn) 和连接相邻顶点的 n 条线段构成的折线。它从原点出发,始终从左向右延伸,最终回到 x 轴:
0=x0<x1<⋯<xn,y0=yn=0.
第 i 条线段用两个整数 di,ki 描述,分别表示它在 x 轴上的投影长度和所在直线的斜率。因此:
xi=xi−1+di,yi=yi−1+kidi.

矿工可以在地面上方的任意点 A 悬挂一盏灯。对于地面上的点 B,如果线段 AB 不穿过地面进入地面下方,就认为灯能够照亮 B。线段 AB 可以接触地面上的点,也可以与地面的某些线段重合。
设 A′ 为 A 正下方的地面上的点。点 A′ 一定被照亮。灯的主区间是从 A′ 出发沿地面行走、且全程都能被这盏灯照亮时可以到达的地面区域。
给定 q 个可能的灯的位置,请分别求出对应主区间的左端点和右端点。
输入格式
第一行包含两个整数 n,q(1≤n,q≤100000),分别表示地面的线段数和询问数。
接下来 n 行,第 i 行包含两个整数 di,ki,满足 1≤di≤109、−109≤ki≤109。
保证由它们得到的顶点满足 0=x0<x1<⋯<xn≤109,y0=yn=0,且 −109≤yi≤109。
接下来 q 行,第 i 行包含两个整数 xi′,yi′,表示一个可能的灯的位置。满足 0≤xi′≤xn、−109≤yi′≤109,且该点严格位于地面上方。
输出格式
输出 q 行,每行两个整数,分别表示对应主区间左端点和右端点的 x 坐标。
保证所求坐标均为整数。
样例 1
输入
4 3
2 1
2 -1
2 1
2 -1
0 2
5 3
4 1
输出
0 2
2 8
2 6
样例 2
输入
8 4
2 0
1 -2
1 4
2 -2
4 0
2 1
1 -1
1 1
5 3
9 -1
3 3
13 4
输出
4 12
4 12
0 4
4 14