| Сириус.2019.Ноябрь.Очный отбор |
|---|
| Finished |
Однажды Георгий пришел в военкомат и провел там весь день. Ему так там понравилось, что на следующий день он пришел туда еще раз!
Чтобы пройти процедуру, необходимо получить $$$k$$$ печатей. За каждой печатью нужно стоять в очереди, причем все печати нужно обязательно получать по порядку (то есть от $$$1$$$-й до $$$k$$$-й). Известно, что $$$i$$$-я печать ставится ровно $$$t_i$$$ времени.
В военкомат пришло $$$n$$$ человек, $$$i$$$-й пришел в момент времени $$$a_i$$$. Как только человек заходит в военкомат, он сразу встает в очередь за первой печатью (если два человека пришли в одно время, то первым встает человек с меньшим номером). Как только кому-то поставили печать, он мгновенно встает в очередь за следующей печатью (а на его место заходит следующий по очереди, если такой есть) или, если он получил $$$k$$$-ю печать, он уходит. Также, некоторые люди очень занятые, поэтому про $$$i$$$-го человека известно, что, если $$$b_i = 0$$$, то он готов ждать сколько угодно, а иначе, если он находится в военкомате хотя бы $$$b_i$$$ времени, то ему надоедает ждать, и он просто покидает военкомат, не закончив.
Разумеется у работников военкомата нет перерыва, и они мгновенно начинают ставить печати каждому, кто к ним заходит.
Георгий хороший математик, поэтому он смог посчитать сколько каждый человек провел времени в военкомате. А сможете ли вы?
В первой строке даются числа $$$n$$$ и $$$k$$$ ($$$1 \le n \cdot k \le 10^5$$$) — количество людей, пришедших в военкомат и количество печатей, которые нужно получить.
В следующей строке идут $$$k$$$ чисел, в $$$i$$$-е число равно $$$t_i$$$ — время, которое нужно, чтобы поставить $$$i$$$-ю печать ($$$1 \le t_i \le 10^9$$$).
Далее идут $$$n$$$ строк, в $$$i$$$-й из них даются два числа $$$a_i$$$ и $$$b_i$$$ — время, в которое $$$i$$$-й человек приходит, и время, которое он готов провести в военкомате, после чего уйдет ($$$1 \leq a_i \leq 10^9, 0 \leq b_i \leq 10^9$$$).
Выведите в единственной строке $$$n$$$ чисел — время, которое $$$i$$$-й человек проведет в военкомате, если он получил все печати, или -1, если он так и не получит последнюю печать.
1 1 1 1 1
1
6 1 17 10 100 3 30 80 59 24 86 59 76 69 15
27 17 21 30 17 -1
В первом примере $$$1$$$-й человек придет ко времени $$$1$$$, проведет там $$$1$$$ единицу времени, после чего ему нужно будет уйти. Но к этому моменту он уже успеет поставить себе печать, поэтому он проведет в военкомате $$$1$$$ единицу времени и получит все печати.
