Олимпиадный тренинг

Задача . B. Евгений и плейлист


Задача

Темы: Бинарный поиск два указателя реализация *1200

Евгений любит слушать музыку. В плейлисте Евгения играет 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 1 2
2 8
1 16 
1
1
2 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

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет