题目描述

小珅同学写了一个数列，这个数列可以分为连续的 n 段，其中第 i 段是 $a_i$ 个 $num_i$ 。然后他找了小泽玩游戏，小泽同学一共会提出 q 个问题，第 i 个问题是问这个数列的第 $k_i$ 个数是多少，你能帮小珅同学回答小泽同学的问题吗

输入格式

第一行，两个正整数小泽同学n,q。

接下来 n 行，每行两个正整数 $a_i$,$num_i$ ，两数之间以一个空格分隔

再接下来 q 行，每行一个正整数 $k_i$

输出格式

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

输入样例 #1

2 3
1 2
2 3
1
2
3

输出样例 #1

2
3
3

输入样例 #2

1 4
1000000000 7
1
2
999999999
1000000000

输出样例 #2

7
7
7
7

输入样例 #3

4 6
2 10
1 20
3 30
4 40
1
2
3
4
6
10

输出样例 #3

10
10
20
30
30
40

数据范围

第一行，两个正整数小泽同学n,q(1≤n,q≤$10^{5}$)。

接下来 n 行，每行两个正整数 $a_i$,$num_i$(1≤$a_i$,$num_i$≤$10^{9}$) ，两数之间以一个空格分隔

再接下来 q 行，每行一个正整数 $k_i$(1≤$k_i$≤∑$a_i$)

对于 30% 的数据，∑$a_i$≤$10^{6}$ 。

对于 70%的数据，1≤n,q≤$10^{3}$ 。

对于 100%的数据，1≤n,q≤$10^{5}$ 。

(1≤n,q≤$10^{5}$)

(1≤$a_i$,$num_i$≤$10^{9}$)

(1≤$k_i$≤∑$a_i$)