Инциденты в Неверморе
ограничение по времени на тест
4.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Академии Невермор по длинному коридору (его можно считать числовой прямой) стоят $$$n$$$ обитателей. У $$$i$$$-го обитателя есть:

- координата на коридоре $$$x_i$$$;
- личный запас ума $$$m_i$$$;
- показатель командной работы $$$z_i$$$;
- особый трюк: он может временно уменьшить свой ум и повысить командную работу.

Формально, у $$$i$$$-го обитателя есть два числа $$$c_i$$$ и $$$a_i$$$. В любой момент (за нулевое время) он может заменить своё текущее значение ума на

$$$$$$\left\lfloor \frac{\text{текущий ум}}{c_i} \right\rfloor$$$$$$

и одновременно увеличить свою командную работу на $$$a_i$$$. Этой операцией можно пользоваться произвольное количество раз, если это выгодно.

Обитатели могут перемещаться по коридору: за единицу времени каждый обитатель может сместиться по прямой на $$$+1$$$ или $$$-1$$$.

Если несколько обитателей в некоторый момент времени оказались в одной и той же точке коридора, они могут объединиться в команду. Тогда:

- ум команды равен сумме умов всех участвующих обитателей;
- командная работа команды равна минимуму по командной работе всех участвующих обитателей.

В академии возникают $$$q$$$ независимых инцидентов. Для каждого инцидента известны:

- координата $$$y_j$$$ — место, где нужно собрать команду;
- требуемый ум $$$s_j$$$;
- требуемая командная работа $$$t_j$$$.

Необходимо определить, за какое минимальное время в точке $$$y_j$$$ можно собрать такую команду из имеющихся обитателей (с учётом их перемещений и применения трюков), чтобы суммарный ум команды был не меньше $$$s_j$$$, а командная работа команды не меньше $$$t_j$$$. Если собрать такую команду невозможно, следует вывести $$$-1$$$.

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

В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$, $$$q$$$ — количество обитателей и количество инцидентов ($$$1 \leq n, q \leq 10^5$$$).

Во второй строке содержатся $$$n$$$ целых чисел — $$$x$$$-координаты обитателей ($$$0 \leq x_i \leq 10^9$$$).

В третьей строке содержатся $$$n$$$ целых чисел $$$m_i$$$ ($$$0 \leq m_i \leq 10^5$$$).

В четвёртой строке содержатся $$$n$$$ целых чисел $$$z_i$$$ ($$$0 \leq z_i \leq 10^5$$$).

В пятой строке содержатся $$$n$$$ целых чисел $$$c_i$$$ ($$$1 \leq c_i \leq 10^5$$$).

В шестой строке содержатся $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq 10^5$$$).

Далее следуют $$$q$$$ строк, в каждой из которых содержатся три целых числа $$$y_j$$$, $$$s_j$$$, $$$t_j$$$ — координата инцидента, требуемый ум и требуемая командная работа соответственно ($$$0 \leq y_j \leq 10^9$$$; $$$0 \leq s_j, t_j \leq 10^{14}$$$).

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

Для каждого из $$$q$$$ инцидентов выведите одно целое число — минимальное время, за которое в точке $$$y_j$$$ может быть собрана команда с суммарным умом не меньше $$$s_j$$$ и командной работой не меньше $$$t_j$$$. Если это невозможно, выведите $$$-1$$$.

Пример

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

    4 60 10 5 710 6 4 31 5 2 42 2 2 33 1 2 15 12 40 6 610 7 45 25 35 15 57 5 4

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

    5
    10
    3
    -1
    -1
    2