题目描述
33DAI 根据平时刷短视频看小游戏广告的经验，设计了一个游戏。
33DAI 初始生命值为 $n$，威胁度为 $0$。有 $m$ 位敌人，第 $i$ 位敌人的战斗力为 $a_i$，胆量为 $b_i$。
33DAI 玩了 $T$ 轮游戏，每次会挑选一个位置 $k$，然后从第 $k$ 个敌人开始，往后一个个对敌人尝试发起战斗：
- 如果当前敌人的胆量小于等于 33DAI 的威胁度，则会被 33DAI 吓坏直接逃跑不战斗，否则就会开始战斗。
- 假设当前与第 $i$ 为敌人进行了战斗，战斗后 33DAI 的生命值就会**减少** $a_i$，然后威胁度会**变为** $b_i$。
- 如果生命值小于等于 $0$，那么 33DAI 被视为被打败了，这轮游戏就结束了。
- 和第 $m$ 位敌人战斗后，就没有敌人了，游戏也就自然结束了。
每轮游戏开始时 33DAI 的生命值都会恢复如初，威胁度会重新归 $0$。所有被吓跑的敌人也都会回来。请你输出每轮游戏 33DAI 最后被谁打败了，如果游戏结束时 33DAI 没有被打败，输出 $0$。
输入
第一行为三个数 $n,m,T$。
接下来 $m$ 行，每行为两个整数，第 $i$ 行为 $a_i,b_i$。
接下来 $T$ 行，第 $i$ 行为第 $i$ 轮游戏的开始位置 $k$。
输出
输出 $T$ 行，即每轮游戏 33DAI 最后被谁打败了，如果没有被打败过输出 $0$。
样例输入输出
输入#1
复制
25 6 1
10 4
8 6
5 3
14 4
9 10
20 4
1
输入#2
复制
19 6 6
10 4
8 6
5 3
14 4
9 10
20 4
1
2
3
4
5
6
提示
【样例1解释】
只进行了一次游戏，从第一个敌人开始，33DAI 的初始生命值 $25$，威胁度 $0$
| 敌人战斗力 | 敌人胆量 | 是否战斗 | 战后生命值 | 战后威胁度 |
|:---:|:---:|:---:|:---:|:---:|
| 10 | 4 | 胆量大于 0，开始战斗 | 15 | 4 |
| 8 | 6 | 胆量大于 4，开始战斗 | 7 | 6 |
| 5 | 3 | 胆量小于 6，被吓跑 | 不变 | 不变 |
| 14 | 4 | 胆量小于 6，又被吓跑 | 不变 | 不变 |
| 9 | 10 | 胆量大于 6，开始 | -2 | 9 |
| 20 | 4 | 游戏已经结束 | 游戏已经结束 | 游戏已经结束 |
因此游戏最后一次战斗是和第 $5$ 位敌人。
【样例2解释】
和样例 1 敌人一样，初始血量不同，从每个敌人都开始打一次。
【数据规模与约定】
对于 $100\%$ 的数据：
- $1\le n\le 10^9$，初始血量
- $1 \le m,T \le 10^5$，敌人数量，游戏轮数
- $1\le a_i\le 1000$，敌人战斗力
- $1\le b_i\le 10^9$，敌人胆量
- $1\le k\le m$，游戏开始的位置
子任务划分：
- 子任务 1（10 分）：保证 $T=1,k=m$。
- 子任务 2（20 分）：保证 $T=1,k=1$。
- 子任务 3（30 分）：保证敌人胆量严格递增。
- 子任务 4（40 分）：没有特殊限制。