Активная подготовка к битве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Карнаж хочет сразиться с Веномом, но для этого ему нужно набрать силы. Он узнал, что поедание некоторых людей положительно влияет на способности симбиотов, и чем сильнее и способнее был человек, тем полезнее будет его съесть. Однако люди имеют неприятное свойство сопротивляться, и если человек достаточно проворен, то он может успеть поднять шум прежде, чем с ним будет покончено, что привлечёт внимание полиции и детектива Патрика Маллигана.

Сейчас сила Карнажа $$$P$$$ равна 1, а полиция ничего не подозревает, и их уровень настороженности $$$C$$$ равен 0. Карнаж может добраться до $$$n$$$ людей, $$$i$$$-го из которых можно описать парой чисел $$$(p_i, c_i)$$$. При попытке съесть $$$i$$$-го человека может случиться одно из двух:

Одновременно можно охотиться только на одну цель, и логично, что каждого человека можно съесть не более одного раза. Порядок, в котором он будет охотиться за жертвами, Карнаж выбирает сам.

На самом деле, Карнаж не знает, насколько опасен Веном, поэтому он делает $$$q$$$ предположений о силе противника: $$$i$$$-е предположение характеризуется потенциально возможной силой Венома $$$x_i$$$. Для каждого предположения найдите минимальную настороженность полиции, которая может получиться при наборе Карнажем силы $$$P \geqslant x_i$$$, или определите, что такую силу набрать невозможно.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ — количество потенциальных жертв Карнажа и количество его предположений о силе Венома ($$$1 \leqslant n \leqslant 10^5$$$; $$$1 \leqslant q \leqslant 10^6$$$).

Следующие $$$n$$$ строк содержат описания людей: в $$$i$$$-й строке через пробел записаны два целых числа $$$p_i$$$ и $$$c_i$$$ — уровень силы $$$i$$$-го человека и потенциальный прирост внимания полиции при охоте на него ($$$1 \leqslant p_i \leqslant 10^9$$$; $$$1 \leqslant c_i \leqslant 10^9$$$).

Следующая строка содержит $$$q$$$ целых чисел $$$x_1, x_2, \ldots, x_q$$$, записанных через пробел. Число $$$x_i$$$ описывает $$$i$$$-е предположение Карнажа о силе Венома ($$$1 \leqslant x_i \leqslant 10^9$$$). Память иногда подводит Карнажа, поэтому одно и то же значение может встречаться в этой последовательности несколько раз.

Выходные данные

Выведите через пробел $$$q$$$ чисел. Число номер $$$i$$$ должно описывать ответ для $$$i$$$-го предположения. Если невозможно набрать силу, не меньшую $$$x_i$$$, ответ равен $$$-1$$$, а иначе — минимальному вниманию полиции к Карнажу после того, как он наберет эту силу.

Примеры

Входные данные
6 5
8 10
10 10
4 4
2 3
8 8
8 5
3 7 32 36 36
Выходные данные
3 4 5 5 5 
Входные данные
9 10
9 8
3 1
2 1
8 9
3 1
5 2
3 1
4 1
10 10
75 53 82 22 6 27 21 86 14 35
Выходные данные
-1 -1 -1 1 1 1 1 -1 1 1