Задача №112124. Варенье
Малыш и Карлсон решили пойти на прогулку. Они знают, что прогулка будет совсем скучной, если перед ней не опустошить несколько банок варенья.
Малыш достал из кладовки N банок варенья и выставил их в ряд. В банке номер i содержится ровно a i грамм варенья. Карлсон немного подумал и решил, что в некоторых банках недостаточно варенья, и что в банке номер i должно быть хотя бы b i грамм варенья.
Выходить из этой ситуации Карлсон хочет в M этапов. На каждом этапе он выбирает числа l , r , x и y , а затем выполняет следующие операции: в банку номер l он добавляет x грамм варенья, в банку номер l + 1 — x + y грамм варенья, в банку номер l + 2 — x + 2· y , и так далее. В банку номер r наш герой добавит x + y ·( r - l ) грамм варенья.
Малышу хочется определить для каждой банки i наименьший номер операции, после которой в ней станет хотя бы b i грамм варенья. Помогите Малышу: найдите соответствующее число для каждой банки.
В первой строке входного файла задано одно число N ( 1 ≤ n ≤ 10 5 ) — количество банок. Во второй строке заданы N чисел a i ( 0 ≤ a i ≤ 2·10 9 ) — изначальное количество варенья в банке номер i . В третьей строке заданы N чисел b i ( 0 ≤ b i ≤ 2·10 9 ) — минимальное количество варенья, которое должно быть в банке номер i .
В четвертой строке задано M ( 0 ≤ M ≤ 10 5 ) — число этапов добавления варенья в банки, которые выполнит Карлсон. В следующих M строках описаны сами этапы в хронологическом порядке. Каждый этап задан четырьмя числами l , r , x и y ( 1 ≤ l ≤ r ≤ N , 0 ≤ x , y ≤ 10 5 ).
Выведите N чисел в одной строке, разделенные пробелом. Число номер i должно быть равно нулю, если в банке номер i изначально было достаточно варенья, номеру этапа, после которого в ней станет хотя бы b i варенья, или - 1 , если даже после выполнения всех этапов, в этой банке будет недостаточно варенья. Этапы нумеруются с единицы.
Оценивание:
-
Первая группа тестов состоит из тестов, для которых выполняется ограничение
N
,
M
≤ 1000
. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет
20
баллов.
-
Вторая группа тестов состоит из тестов, для которых во всех этапах добавления варенья выполняется ограничение
y
= 0
. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет
40
баллов.
- Третья группа тестов состоит из тестов, для которых нет дополнительных ограничений. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.
5 5 4 4 2 1 7 7 4 7 7 3 1 2 2 0 2 5 1 1 3 4 2 2
1 2 0 3 -1