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.

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.