题目背景

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

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

题目描述

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

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

顶点编号 $0$ 位于点 $(0, 0)$。第 $i$ 个线段由其在水平轴上的投影长度 $d_i$ 与斜率 $k_i$ 给出。于是，若编号为 $i - 1$ 的顶点坐标为 $(x_{i-1}, y_{i-1})$，则第 $i$ 个顶点的坐标可按如下计算：$(x_{i-1} + d_i, y_{i-1} + k_i \cdot d_i)$。最后一个顶点的 $y$ 坐标为 $0$，即 $y_n = 0$。

:::align{center} :::

若点 $A$ $(x_A, y_A)$ 到点 $B$ $(x_B, y_B)$ 的线段上没有任何一点位于折线下方（严格意义上），则称点 $A$ 从点 $B$ 是直线可见的。

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

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

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

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 400\,000$）——折线的线段数量以及塔的位置方案数量。

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

接下来的 $n$ 行中，每行包含两个整数 $d_i, k_i$（$1 \le d_i \le C$；$-C \le k_i \le C$）——第 $i$ 个线段在水平轴上的投影长度与斜率（$0 = x_0 < x_1 < \cdots < x_i < \cdots < x_n \leq C$；$y_0 = y_n = 0$；$-C \le y_i \le C$）。

接下来的 $m$ 行中，每行包含两个整数 $u_j, v_j$（$0 \leq u_j \leq C$，$-C \leq v_j \leq C$）——第 $j$ 个方案中塔的上端点坐标。

输出格式

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

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

3 8

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

1 6
0 7
0 6

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

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

提示

样例解释

:::align{center}

样例 1 示意 :::

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

:::align{center}

样例 2 示意 :::

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

:::align{center}

样例 3 示意 :::

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

:::align{center}

样例 4 示意 :::

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

数据范围

子任务编号	分值	$n, m$	$C$	其他限制	必须通过的子任务
1	9	$1 \le n, m \le 100$	$C = 10^4$	$k_i = \pm 1$
2					1
3	10	$1 \le n, m \le 3000$	$C = 10^9$		1, 2
4	11	$1 \le n, m \le 100\,000$		$k_i = \pm 1$	1
5				所有塔的下端点重合
6	12			所有塔的上端点共线于同一条水平直线上
7	21				1–6
8	17	$1 \le n, m \le 400\,000$			1–7

翻译由 ChatGPT-5 完成