尤金妮喜欢听音乐。他的播放列表中有 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