图图 根据平时刷短视频看小游戏广告的经验，设计了一个游戏。

图图 初始生命值为 n，威胁度为 0。有 m 位敌人，第 i 位敌人的战斗力为 a_i，胆量为 b_i。

图图 玩了 T 轮游戏，每次会挑选一个位置 k，然后从第 k 个敌人开始，往后一个个对敌人尝试发起战斗：

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

每轮游戏开始时 图图 的生命值都会恢复如初，威胁度会重新归 0。所有被吓跑的敌人也都会回来。请你输出每轮游戏 图图 最后被谁打败了，如果游戏结束时 图图 没有被打败，输出 0。

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

第二行为 m 个整数 a_1\sim a_m。

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

输出 T 行，即每轮游戏 图图 最后被谁打败了，如果没有被打败过输出 0。

样例解释1

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

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

样例解释2

和样例 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 分）：没有特殊限制。