E. Прогнозирование популярности
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Представьте, что вы работаете в Берфликсе — крупнейшем стриминговом сервисе в Берляндии, занимающимся распространением фильмов. Аудитория данного сервиса состоит из $$$n$$$ пользователей, и про каждого из них известны его некоторые предпочтения: уровень экшена в фильме $$$a_i$$$ и уровень драмы $$$d_i$$$.

Ваша текущая задача — попытаться предсказать популярность некоторого фильма. Пусть интересующий вас фильм содержит $$$ac$$$ «единиц» экшена и $$$dr$$$ «единиц» драмы (данные любезно предоставлены командой аналитиков). Если в фильме и экшена, и драмы не меньше пороговых значений некоторого пользователя, то он обязательно посмотрит данный фильм.

Если же фильм не дотягивает по экшену или по драме, пользователь будет колебаться. Однако склонить к просмотру его может популярность данного фильма у других зрителей. В результате долгих обсуждений ваша команда выбрала следующую модель развития событий.

Пусть $$$p$$$ — количество человек, которые уже посмотрели данный фильм (первоначально $$$p = 0$$$). Будем считать, что пользователю $$$i$$$ фильм подходит, если $$$\max(a_i - ac, 0) + \max(d_i - dr, 0) \le p$$$.

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

В результате данный процесс завершится, когда: либо все посмотрят данный фильм, либо ни кому из оставшихся зрителей он не подходит. И ваша задача как раз в том, чтобы посчитать, сколько человек в конечном итоге посмотрит данный фильм.

Осталась последняя проблема — оценка предпочтений пользователей постоянно меняется. А именно, приходит $$$m$$$ запросов на изменение значений $$$a_k$$$ и $$$d_k$$$ для какого-то пользователя $$$k$$$, и вам нужно пересчитывать конечную популярность фильма $$$p$$$ после каждого изменения.

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

В первой строке заданы два числа $$$ac$$$ и $$$dr$$$ ($$$1 \le ac, dr \le 10^6$$$) — оценка экшена и драмы фильма.

Во второй строке задано одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — количество пользователей Берфликса.

В третьей строке заданы $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — предпочтения пользователей по экшену.

В четвертой строке заданы $$$n$$$ чисел $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le 10^6$$$) — предпочтения пользователей по драме.

В пятой строке задано одно целое число $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — количество изменений в предпочтениях пользователей.

Далее в $$$m$$$ строках заданы сами изменения в формате:

  • «$$$k_j$$$ $$$na_j$$$ $$$nd_j$$$» ($$$1 \le k_j \le n$$$; $$$1 \le na_j, nd_j \le 10^6$$$), где $$$na_j$$$ — новое предпочтение $$$k_j$$$-го пользователя по экшену, а $$$nd_j$$$ — по драме.
Выходные данные

Для каждого запроса изменения выведите — общее ожидаемое количество просмотров фильма $$$p$$$ после обновления информации о соответствующем пользователе.

Пример
Входные данные
20 25
4
1 22 1 30
1 22 50 30
5
3 1 25
2 23 22
4 10 27
1 21 21
3 20 26
Выходные данные
3
2
4
4
0
Примечание

Рассмотрим первый запрос. Первому и третьему зрителю фильм уже подходит, а потому они его посмотрят, увеличив популярность $$$p$$$ на $$$2$$$. При $$$p = 2$$$ фильм станет подходить второму зрителю. В результате и он его посмотрит, увеличив популярность еще на $$$1$$$. Однако, $$$4$$$-му зрителю фильм все еще не подходит, так как $$$\max(30 - 20, 0) + \max(30 - 25, 0) \gt 3$$$.

Таким образом, после первого запроса, фильм посмотрят $$$3$$$ человека.