| Codeforces Round 182 (Div. 2) |
|---|
| Закончено |
Евгений любит слушать музыку. В плейлисте Евгения играет n песен. Известно, что песня номер i имеет продолжительность ti минут. Каждую песню плейлиста Евгений слушает, возможно, более одного раза. Песню номер i он слушает ci раз. Плейлист Евгения построен следующим образом: сначала c1 раз играет песня номер 1, потом c2 раз играет песня номер 2, ..., в конце cn раз играет песня номер n.
Евгений выписал себе на листочек m моментов времени, в которые ему понравились песни. Теперь для каждого такого момента, он хочет узнать номер песни, которая играла в этот момент времени. Момент времени x обозначает, что Евгений хочет знать, какая песня играла в x-ую от начала минуту прослушивания плейлиста.
Помогите Евгению, выведите требуемые номера песен.
В первой строке заданы два целых числа n, m (1 ≤ n, m ≤ 105). В следующих n строках заданы пары целых чисел. В i-ой строке записаны целые числа ci, ti (1 ≤ ci, ti ≤ 109) — описание плейлиста. Гарантируется, что суммарная продолжительность плейлиста не более 109 
.
В следующей строке записаны m целых положительных чисел v1, v2, ..., vm, которые описывают времена, выписанные Евгением. Гарантируется, что не существует момента времени vi, когда музыка уже не играла. Гарантируется, что vi < vi + 1 (i < m).
Момент времени vi обозначает, что Евгений хочет знать, какая песня играла в vi-ую от начала минуту прослушивания плейлиста.
Выведите m целых чисел — i-ое число должно быть равно номеру песни, которая играла в vi минуту от начала прослушивания плейлиста.
1 2
2 8
1 16
1
1
4 9
1 2
2 1
1 1
2 2
1 2 3 4 5 6 7 8 9
1
1
2
2
3
4
4
4
4
