You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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$。

25 6 1
10 4
8 6
5 3
14 4
9 10
20 4
1

5

样例解释

只进行了一次游戏，从第一个敌人开始，33DAI 的初始生命值 $25$，威胁度 $0$

因此游戏最后一次战斗是和第 $5$ 位敌人。

19 6 6
10 4
8 6
5 3
14 4
9 10
20 4
1
2
3
4
5
6

5
0
4
5
0
6

和样例 1 敌人一样，初始血量不同，从每个敌人都开始打一次。

样例 3

一个简单的随机大数据

• 3.in
• 3.out

数据规模与约定

对于 $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 分）：没有特殊限制。