Eugeny and Play List

题意翻译

Eugeny 的歌单中有 $n$ 首歌，其中第 $i$ 首歌播放 $c_i$ 次，每次播放持续 $t_i$ 分钟。Eugeny 会按顺序播放这 $n$ 首歌，也就是说，Eugeny 会先播放第 $1$ 首歌 $c_1$ 次，第 $2$ 首歌 $c_2$ 次，依此类推。然后有 $m$ 个问题，每个问题为一个正整数 $v_i$，表示第 $v_i$ 分钟时，Eugeny 在播放第几首歌？ ### 输入格式 第一行两个正整数 $n,m$（$1 \le n,m \le 10^5$）。 随后 $n$ 行，第 $i+1$ 行有 $2$ 个正整数 $c_i,t_i$（$1 \le c_i \le t_i \le 10^9$，且保证 $\displaystyle\sum_{i=1}^n c_i \times t_i \le 10^9$）。 随后一行 $m$ 个正整数表示 $v_1$ 到 $v_n$，保证按升序给出，且对于每个询问，整个歌单的所有歌曲都还没有放完。 ### 输出格式 对于每个询问，输出一行，表示第 $v_i$ 分钟时，正在放歌单中的第几首歌曲。

题目描述

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}&lt;v_{i+1} $ $ (i&lt;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.

输入输出样例

输入样例 #1

1 2
2 8
1 16

输出样例 #1

1
1

输入样例 #2

4 9
1 2
2 1
1 1
2 2
1 2 3 4 5 6 7 8 9

输出样例 #2

1
1
2
2
3
4
4
4
4