#214343. [ROI 2016 Day1] 人烟之山

译自 ROI 2016 Day1 T4. Обитаемые горы

改编自 Arkadi Strugatsky 与 Boris Strugatsky 的科幻中篇《人烟之岛》。

不知名之父国的政府计划在与洪提亚接壤的多山地区修建一座反弹道防御塔。

该地区的一段山脉以一条折线表示，这条折线由 个线段组成，依次连接 个顶点，这些顶点按 坐标递增排列。顶点编号为 到 ，线段编号为 到 ，其中第 个线段连接编号为 与 的两个顶点。

顶点编号 位于点 。第 个线段由其在水平轴上的投影长度 与斜率 给出。于是，若编号为 的顶点坐标为 ，则第 个顶点的坐标可按如下计算：。最后一个顶点的 坐标为 ，即 。

:::align{center} :::

若点 到点 的线段上没有任何一点位于折线下方（严格意义上），则称点 从点 是直线可见的。

塔是一条垂直的非零长度线段，其下端点位于折线上。若塔的上端点处于某位公民的直线可见范围内，则该公民感到安全。

设塔的上端点在 。考虑两名侦察兵，他们从塔的下端点分别向西（ 坐标减小方向）与向东（ 坐标增大方向）出发。每名侦察兵沿着山脉表面奔跑，直到进一步移动会使塔的上端点离开其直线可见范围，或直到到达山脉的边界为止。

政府准备了 种塔的位置方案，每个方案由两个整数 表示——即塔的上端点坐标。要求编写程序，对每个方案分别确定两名侦察兵能跑到的点的 坐标。

第一行包含两个整数 和 （）——折线的线段数量以及塔的位置方案数量。

随后的输入约束取决于常数 的取值， 可为 或 ，具体由子任务决定（见评分表）。

接下来的 行中，每行包含两个整数 （；）——第 个线段在水平轴上的投影长度与斜率（；；）。

接下来的 行中，每行包含两个整数 （，）——第 个方案中塔的上端点坐标。

输出共 行，每行包含两个整数 与 ——分别为第 个方案中向西和向东奔跑的侦察兵能到达的点的 坐标。保证 与 都为整数。

样例输入 1

6 1
3 1
2 -1
1 1
1 -1
1 1
2 -1
5 3

样例输出 1

3 8

样例输入 2

5 3
1 1
1 -2
2 0
2 1
1 -1
3 0
3 5
3 3

样例输出 2

1 6
0 7
0 6

样例输入 3

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

样例输出 3

0 4
1 9
4 10
1 10

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

样例输出 4

0 6
4 9
0 10
6 9

样例解释

:::align{center}

样例 1 示意 :::

请注意，根据题目中的定义，线段 与 之间的所有点均处于塔的上端点的直线可见范围内。

:::align{center}

样例 2 示意 :::

在该测试中，所有方案的塔的下端点都位于同一点。

:::align{center}

样例 3 示意 :::

在该测试中，所有方案的塔的上端点都位于同一条水平直线上。请注意，塔的下端点可以位于山脉链的端点处。

:::align{center}

样例 4 示意 :::

在第四个测试中说明，在不知名之父国，整条山脉链可能完全位于其两端点的高度之下。

数据范围

翻译由 ChatGPT-5 完成