人烟之山
题号：NC53331
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
Special Judge, 64bit IO Format: %lld

题目描述 

基于斯特鲁伽茨基兄弟的小说《人烟之岛》。 译者没时间翻译完整题面了，泥萌先甭看故事了
roi16D1.sans.png
某地地形可用n段折线来表示（下文称之为多段线），这n段折线连接了n+1个拐点，且保证没有垂直线。我们将拐点从左到右依次编为号。我们将最左侧的点（即0号点）设为原点，然后给出每一段的射影长度（即该线段的两个端点的横坐标之差）和斜率。保证n号点的纵坐标为0.
在某些位置将建起瞭望塔，瞭望塔上有一个或一些瞭望台。假设已知点A和点B，如果线段AB上没有点严格位于多段线以下，那么我们称点A可以看到点B。
该地共有q个瞭望台。给出所有瞭望台的位置。对于试求：从j号瞭望台的塔基向左/右走，一直走到什么地方时还能看到该瞭望台，而再走远一点点就看不到了。（我们称之为该瞭望台的视界。）

输入描述:

第一行有两个整数n,q。
第二行有一个整数C,保证或。这个数会提示下面输入的数据的范围。
接下来n行，每行两个整数d_i,k_i。
接下来q行，每行两个整数u_j,v_j表示瞭望台的坐标。

输出描述:

共q行，每行两个整数，表示该瞭望台的视界。
示例1

输入

复制 
6 1
3 1
2 -1
1 1
1 -1
1 1
2 -1
5 3

输出

复制 
3 8

说明

sample1.png
示例2

输入

复制 
5 3
1 1
1 -2
2 0
2 1
1 -1
3 0
3 5
3 3

输出

复制 
1 6
0 7
0 6

说明


sample2.png

示例3

输入

复制 
6 4
1 2
2 -2
1 1
1 -2
4 1
1 -1
1 4
3 4
10 4
7 4

输出

复制 
0 4
1 9
4 10
1 10

说明

sample3.png
示例4

输入

复制 
8 4
1 -3
2 0
1 1
2 0
1 -3
1 3
1 2
1 0
2 -2
6 -1
6 4
7 -4

输出

复制 
0 6
4 9
0 10
6 9

说明

sample4.png

备注:


CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/3063