#P18820. [Croatian CPC2016] Rudar

[Croatian CPC2016] Rudar

[Croatian CPC2016] Rudar

题目描述

矿洞的地面是一条由 n+1n+1 个顶点 (x0,y0),(x1,y1),…,(xn,yn)(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n) 和连接相邻顶点的 nn 条线段构成的折线。它从原点出发,始终从左向右延伸,最终回到 xx 轴:

0=x0<x1<⋯<xn,y0=yn=0.0=x_0<x_1<\cdots<x_n,\qquad y_0=y_n=0.

第 ii 条线段用两个整数 di,kid_i,k_i 描述,分别表示它在 xx 轴上的投影长度和所在直线的斜率。因此:

xi=xi−1+di,yi=yi−1+kidi.x_i=x_{i-1}+d_i,\qquad y_i=y_{i-1}+k_i d_i.

两个样例的示意图

矿工可以在地面上方的任意点 AA 悬挂一盏灯。对于地面上的点 BB,如果线段 ABAB 不穿过地面进入地面下方,就认为灯能够照亮 BB。线段 ABAB 可以接触地面上的点,也可以与地面的某些线段重合。

设 A′A' 为 AA 正下方的地面上的点。点 A′A' 一定被照亮。灯的主区间是从 A′A' 出发沿地面行走、且全程都能被这盏灯照亮时可以到达的地面区域。

给定 qq 个可能的灯的位置,请分别求出对应主区间的左端点和右端点。

输入格式

第一行包含两个整数 n,qn,q(1≤n,q≤1000001\le n,q\le100000),分别表示地面的线段数和询问数。

接下来 nn 行,第 ii 行包含两个整数 di,kid_i,k_i,满足 1≤di≤1091\le d_i\le10^9、−109≤ki≤109-10^9\le k_i\le10^9。

保证由它们得到的顶点满足 0=x0<x1<⋯<xn≤1090=x_0<x_1<\cdots<x_n\le10^9,y0=yn=0y_0=y_n=0,且 −109≤yi≤109-10^9\le y_i\le10^9。

接下来 qq 行,第 ii 行包含两个整数 xi′,yi′x'_i,y'_i,表示一个可能的灯的位置。满足 0≤xi′≤xn0\le x'_i\le x_n、−109≤yi′≤109-10^9\le y'_i\le10^9,且该点严格位于地面上方。

输出格式

输出 qq 行,每行两个整数,分别表示对应主区间左端点和右端点的 xx 坐标。

保证所求坐标均为整数。

样例 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