1698 - 【入门】数列

周周写了一个数列,这个数列可以分为连续的 n 段,其中第 i 段是 a_inum_i 。然后他找了玩仔玩游戏,玩仔一共会提出 q 个问题,第 i 个问题是问这个数列的第 k_i 个数是多少,你能帮周周回答玩仔的问题吗?

输入

第一行,两个正整数 n, q(1 \leq n, q \leq 10 ^ 5)

接下来 n 行,每行两个正整数 a_i, num_i(1 \leq a_i, num_i \leq 10 ^ 9)

再接下来 q 行,每行一个正整数 k_i(1 \leq k_i \leq \sum{a_i})

输出

输出 q 行,每行一个整数,表示每次询问的结果。

数据范围 对于 30\% 的数据,\sum{a_i} \leq 10 ^ 6

对于 70\% 的数据,1 \leq n, q \leq 10 ^ 3

对于 100\% 的数据,1 \leq n, q \leq 10 ^ 5

样例

输入

2 3
1 2
2 3
1
2
3

输出

2
3
3

提示

a 做前缀和,对于每次询问,在 a 中找到大于等于 k 的最左边的位置,对应的数字就是答案。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题