Испаньола наконец-то приблизилась к Острову Сокровищ! Шлюпка пиратов уже отправилась в сторону острова и отплыла от корабля на $$$D$$$ футов. Шлюпка Джима только что спустилась на воду и находится в одной точке с кораблём.
Следующие $$$n$$$ секунд обе лодки будут двигаться прямолинейно в сторону острова. Джим точно знает, что в секунду номер $$$i$$$ шлюпка пиратов сдвинется в сторону острова на $$$b_i$$$ футов. При этом шлюпка Джима в секунду номер $$$i$$$ может сдвинуться в сторону острова на любое целое число футов от $$$0$$$ до $$$a_i$$$ по усмотрению Джима. Считайте, что в течение каждой секунды обе лодки движутся равномерно.
Джим хочет обогнать шлюпку пиратов как можно раньше так, чтобы после этого пираты никогда не догнали Джима. Формально, пусть $$$t$$$ ($$$1 \leq t \leq n$$$) — наименьший номер секунды, такой, что в её конце шлюпка Джима была строго ближе к острову, чем шлюпка пиратов. Джим хочет, чтобы начиная с этого момента и вплоть до конца $$$n$$$-й секунды его шлюпка была строго ближе к острову, чем шлюпка пиратов. Из всех возможных $$$t$$$ он хочет выбрать наименьшее.
Однако Джим точно не знает, чему равно расстояние $$$D$$$. У него есть $$$q$$$ предположений $$$d_1, d_2, \ldots, d_q$$$ чему равно $$$D$$$. Он хочет знать наименьшее возможное число $$$t$$$ для каждого своего предположения.
В первой строке содержатся два целых числа $$$n$$$ и $$$q$$$ — количество секунд и количество предположений Джима ($$$1 \leq n \leq 10^5, 1 \leq q \leq 10^5$$$).
Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — максимальные возможные расстояния, которые может проплыть шлюпка Джима в каждую из секунд ($$$0 \leq a_i \leq 10^9$$$).
В третьей строке содержатся $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ — расстояния, которые проплывёт шлюпка пиратов ($$$0 \leq b_i \leq 10^9$$$).
В четвёртой строке содержатся $$$q$$$ целых чисел $$$d_1, d_2, \ldots, d_q$$$ — предполагаемые изначальные расстояния лодки пиратов до корабля ($$$1 \leq d_i \leq 10^9$$$).
В $$$q$$$ строках выведите одно целое число — ответ на каждое предположение Джима.
Если Джим сможет обогнать пиратов в конце секунды $$$t$$$ так, что пираты никогда его не догонят, то выведите число $$$t$$$ ($$$1 \leq t \leq n$$$). Из всех подходящих чисел $$$t$$$ выведите наименьшее. Если план Джима выполнить невозможно, выведите $$$-1$$$.
10 107 4 7 0 5 6 4 4 5 45 3 5 1 2 3 3 7 2 01 2 3 4 5 6 7 8 14 15
1 2 3 5 5 5 6 10 10 -1
1 4411 2 3 4
1 1 -1 -1
