A9037 | Eugeny and Play List

Eugeny 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.

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.

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.