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.

题目描述

小Y在和外星人大战！！！
小Y的初始生命值为 $n$，威胁度为 $0$。有 $m$ 位外星人，第 $i$ 位外星人的战斗力为 $a_i$，胆量为 $b_i$。

小Y打了 $T$ 轮外星人，每次会挑选一个位置 $k$，然后从第 $k$ 个外星人开始，往后一个个对敌人尝试发起战斗：

• 如果当前外星人的胆量小于等于小Y的威胁度，则会被小Y吓坏直接逃跑不战斗，否则就会开始战斗。
• 假设当前与第 $i$ 为外星人进行了战斗，战斗后小Y的生命值就会减少 $a_i$，然后威胁度会变为 $b_i$。
• 如果生命值小于等于 $0$，那么小Y被视为被打败了，这轮游戏就结束了。
• 和第 $m$ 位外星人战斗后，就没有外星人了，战争也就自然胜利了。

因为有时间守护者的关系，每次开始打外星人之前小Y的生命值都会恢复如初，威胁度会重新归 $0$。所有被吓跑的外星人也都会回来。请你输出每轮游戏小Y最后被谁打败了，如果胜利时小Y没有被打败，输出 $0$。

输入格式

第一行为三个数 $n,m,T$。

接下来 $m$ 行，每行为两个整数，第 $i$ 行为 $a_i,b_i$。

接下来 $T$ 行，第 $i$ 行为第 $i$ 轮开始位置 $k$。

输出格式

输出 $T$ 行，即每轮开始时小Y最后被谁打败了，如果没有被打败过输出 $0$。

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

5

样例解释

只进行了一次游戏，从第一个外星人开始，小Y的初始生命值 $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 外星人一样，初始血量不同，从每个敌人都开始打一次。

数据规模与约定

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