Варенье

Малыш и Карлсон решили пойти на прогулку. Они знают, что прогулка будет совсем скучной, если перед ней не опустошить несколько банок варенья.

Малыш достал из кладовки $N$ банок варенья и выставил их в ряд. В банке номер $i$ содержится ровно $a_i$ грамм варенья. Карлсон немного подумал и решил, что в некоторых банках недостаточно варенья, и что в банке номер $i$ должно быть хотя бы $b_i$ грамм варенья.

Выходить из этой ситуации Карлсон хочет в $M$ этапов. На каждом этапе он выбирает числа $l$, $r$, $x$ и $y$, а затем выполняет следующие операции: в банку номер $l$ он добавляет $x$ грамм варенья, в банку номер $l + 1$ --- $x + y$ грамм варенья, в банку номер $l + 2$ --- $x + 2 \cdot y$, и так далее. В банку номер $r$ наш герой добавит $x + y \cdot (r - l)$ грамм варенья.

Малышу хочется определить для каждой банки $i$ наименьший номер операции, после которой в ней станет хотя бы $b_i$ грамм варенья. Помогите Малышу: найдите соответствующее число для каждой банки.

В первой строке входного файла задано одно число $N$ ($1 \le n\le 10^5$) --- количество банок. Во второй строке заданы $N$ чисел $a_i$ ($0 \le a_i \le 2 \cdot 10^9$) --- изначальное количество варенья в банке номер $i$. В третьей строке заданы $N$ чисел $b_i$ ($0 \le b_i \le 2 \cdot 10^9$) --- минимальное количество варенья, которое должно быть в банке номер $i$.

В четвертой строке задано $M$ ($0 \le M \le 10^5$) --- число этапов добавления варенья в банки, которые выполнит Карлсон. В следующих $M$ строках описаны сами этапы в хронологическом порядке. Каждый этап задан четырьмя числами $l$, $r$, $x$ и $y$ ($ 1 \le l \le r \le N$, $0 \le x, y \le 10^5$).

Выведите $N$ чисел в одной строке, разделенные пробелом. Число номер $i$ должно быть равно нулю, если в банке номер $i$ изначально было достаточно варенья, номеру этапа, после которого в ней станет хотя бы $b_i$ варенья, или $-1$, если даже после выполнения всех этапов, в этой банке будет недостаточно варенья. Этапы нумеруются с единицы.