No tag edit access

B. Eugeny and Play List

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputEugeny loves listening to music. He has *n* songs in his play list. We know that song number *i* has the duration of *t*_{i} minutes. Eugeny listens to each song, perhaps more than once. He listens to song number *i* *c*_{i} times. Eugeny's play list is organized as follows: first song number 1 plays *c*_{1} times, then song number 2 plays *c*_{2} times, ..., in the end the song number *n* plays *c*_{n} times.

Eugeny took a piece of paper and wrote out *m* moments of time when he liked a song. Now for each such moment he wants to know the number of the song that played at that moment. The moment *x* means that Eugeny wants to know which song was playing during the *x*-th minute of his listening to the play list.

Help Eugeny and calculate the required numbers of songs.

Input

The first line contains two integers *n*, *m* (1 ≤ *n*, *m* ≤ 10^{5}). The next *n* lines contain pairs of integers. The *i*-th line contains integers *c*_{i}, *t*_{i} (1 ≤ *c*_{i}, *t*_{i} ≤ 10^{9}) — the description of the play list. It is guaranteed that the play list's total duration doesn't exceed 10^{9} .

The next line contains *m* positive integers *v*_{1}, *v*_{2}, ..., *v*_{m}, that describe the moments Eugeny has written out. It is guaranteed that there isn't such moment of time *v*_{i}, when the music doesn't play any longer. It is guaranteed that *v*_{i} < *v*_{i + 1} (*i* < *m*).

The moment of time *v*_{i} means that Eugeny wants to know which song was playing during the *v*_{i}-th munite from the start of listening to the playlist.

Output

Print *m* integers — the *i*-th number must equal the number of the song that was playing during the *v*_{i}-th minute after Eugeny started listening to the play list.

Examples

Input

1 2

2 8

1 16

Output

1

1

Input

4 9

1 2

2 1

1 1

2 2

1 2 3 4 5 6 7 8 9

Output

1

1

2

2

3

4

4

4

4

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/24/2017 09:11:29 (p1).

Desktop version, switch to mobile version.
User lists

Name |
---|