题目描述

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

输入格式

第一行，两个正整数小泽同学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)

输出格式

输出 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} 。