← 返回题目列表

Codeforces · 302/B

B. 尤金妮和播放列表

中文机器翻译题面 查看原题

尤金妮喜欢听音乐。他的播放列表中有 n 首歌曲。我们知道第 i 首歌曲的持续时间为 ti 分钟。尤金妮听每首歌,也许不止一次。他听了 i ci 首歌曲。 Eugeny 的播放列表组织如下:首先歌曲 1 播放 c1 次,然后歌曲 2 播放 c2 次,...,最后歌曲 n 播放 cn 次。

尤金尼拿了一张纸,写下了他喜欢一首歌的 m 个时刻。现在,对于每个这样的时刻,他都想知道当时播放的歌曲的编号。时刻 x 表示 Eugeny 想知道在他收听播放列表的第 x 分钟期间正在播放哪首歌。

帮助尤金妮计算所需的歌曲数量。

输入

第一行包含两个整数 n, m (1 ≤ n, m ≤ 105)。接下来的 n 行包含整数对。第 i 行包含整数 ci, ti (1 ≤ ci, ti ≤ 109) — 播放列表的描述。保证播放列表的总时长不超过 109 $$(\sum_{i=1}^{n} c_i \cdot t_i \leq 10^9)$$。

下一行包含 m 个正整数 v1, v2, ..., vm,描述 Eugeny 写出的时刻。保证不存在音乐不再播放的时刻vi。保证 vi < vi + 1 (i < m)。

时间 vi 的时刻意味着 Eugeny 想知道从开始收听播放列表开始的第 vi 分钟期间正在播放哪首歌。

输出

打印 m 个整数 — 第 i 个数字必须等于 Eugeny 开始收听播放列表后第 vi 分钟内播放的歌曲的编号。

示例

输入 #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