521. Rohan and his Playlist

0

Medium

Rohan 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. Rohan listens to each song, perhaps more than once. He listens to song number `i` **c** times. Rohan's play list is organized as follows: first song number 1 plays c1 times, then song number 2 plays c2 times, ....., in the end the song number n plays c_{n}times. Rohan 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 Rohan wants to know which song was playing during the ***x-th*** minute of his listening to the play list. Help Rohan and calculate the required numbers of songs.Input Format

The first line contains two integers n, m .

The next n lines contain pairs of integers. The i-th line contains integers c

The next n lines contain pairs of integers. The i-th line contains integers c

_{i}, t_{i}— 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 v1, v2, ..., vm, that describe the moments Rohan 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 vi < vi + 1 (i < m). The moment of time v_{5}means that Rohan wants to know which song was playing during the v_{i}-th minute from the start of listening to the playlist.Output Format

Print m integers — the i-th number must equal the number of the song that was playing during the v

_{i}-th minute after Rohan started listening to the play list.Example

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

Constraints

1 ≤ n, m ≤ 10

1 ≤ ci, ti ≤ 10

^{5}1 ≤ ci, ti ≤ 10

^{9}Loading...

View Submissions

Console