时空限制

2S/512M

题目描述

数轴上有 $n$ 个点正在进行周期性的往返运动。

第 $i$ 个点 $(1 \le i \le n)$ 的运动区间是 $[x_i, x_i + L]$。所有点的运动区间长度相同，均为 $L$。

在第 $0$ 秒时：

• 若 $c_i = 0$，则第 $i$ 个点位于 $x_i$，且其初始运动方向向右；
• 若 $c_i = 1$，则第 $i$ 个点位于 $x_i + L$，且其初始运动方向向左。

所有的点每秒移动 $1$ 个单位长度。当任意一个点到达其运动区间的端点时，它会立刻调头反向移动。

现在有 $q$ 个询问，每个询问给出时间 $t$ 和一个整数 $k$，请你求出在第 $t$ 秒时，所有点当前位置中的第 $k$ 小值。

格式

输入格式

第一行包含三个正整数 $n$、$q$ 和 $L$，分别表示点的个数、询问的个数以及区间的长度。

接下来 $n$ 行，每行包含两个整数 $x_i$ 和 $c_i$，描述第 $i$ 个点的运动区间起点和初始方向。

接下来 $q$ 行，每行包含两个整数 $t_j$ 和 $k_j$，描述第 $j$ 次询问的时间和所需的排名。

输出格式

对于每个询问，输出一行一个整数，表示在第 $t$ 秒时所有点位置中的第 $k$ 小值。

样例

样例输入 #1

5 4 10
0 0
7 0
3 1
12 1
20 0
0 3
3 2
12 4
20 5

样例输出 #1

13
10
15
22

样例解释 #1

对于各个询问：

1. $t = 0, k = 3$：此时各点位置为 $0, 7, 13, 22, 20$。从小到大排序为 $0, 7, 13, 20, 22$，第 $3$ 小值为 $13$。
2. $t = 3, k = 2$：此时各点位置为 $3, 10, 10, 19, 23$。从小到大排序为 $3, 10, 10, 19, 23$，第 $2$ 小值为 $10$。
3. $t = 12, k = 4$：此时各点位置为 $8, 15, 5, 14, 28$。从小到大排序为 $5, 8, 14, 15, 28$，第 $4$ 小值为 $15$。
4. $t = 20, k = 5$：运动周期为 $2L = 20$ 秒，此时所有点回到了第 $0$ 秒的位置，即 $0, 7, 13, 22, 20$。从小到大排序后，第 $5$ 小值为 $22$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^5$，$1 \le L \le 10^9$，$0 \le x_i \le 10^9$，$c_i \in \{0, 1\}$，$0 \le t_j \le 10^{18}$，$1 \le k_j \le n$。