Drown in Programming

Time Limit: 1 Second    Memory Limit: 131072 KB

Programming is one of the most interesting activities for Milad. He has done lots of programming projects till now (Specially, .Net Projects). Each project p_i takes him d_i days to be finished using a specific algorithm. He may be asked to write it in a_i different algorithms (Each different algorithm takes the same amount of days d­_i). Milad never works on two projects in a day.

Now he wants to know what project he had been working on, in a certain day.

Input

In the first line of each test case, there are two numbers n and m which are number of projects and number of questions Milad wants to know its answer, respectively (1 <= n, m <= 10⁵).

The ith line of the following n lines specifies d_i and a_i for project p_i (1 <= d_i, a_i <= 10⁹). It is guaranteed that total number of days for all projects does not exceeds 10⁹.

In the last line of each test case, there are m space separated numbers each denotes the day’s number in which Milad wants to know which project he had been working on.

The line “0 0” (Without quotes) indicates end of test cases.

Output

In each test case, print the project’s number he had been working on for day(s) he asks, each in a separate line.

Sample Input

3 3
1 1
1 1
1 1
1 2 3
3 5
1 1
2 2
3 3
1 3 2 4 9
0 0

Sample Output

1
2
3
1
2
2
2
3

Submit