Представьте, что вы работаете в Берфликсе — крупнейшем стриминговом сервисе в Берляндии, занимающимся распространением фильмов. Аудитория данного сервиса состоит из $$$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$$$ строках заданы сами изменения в формате:
Для каждого запроса изменения выведите — общее ожидаемое количество просмотров фильма $$$p$$$ после обновления информации о соответствующем пользователе.
20 2541 22 1 301 22 50 3053 1 252 23 224 10 271 21 213 20 26
3 2 4 4 0
Рассмотрим первый запрос. Первому и третьему зрителю фильм уже подходит, а потому они его посмотрят, увеличив популярность $$$p$$$ на $$$2$$$. При $$$p = 2$$$ фильм станет подходить второму зрителю. В результате и он его посмотрит, увеличив популярность еще на $$$1$$$. Однако, $$$4$$$-му зрителю фильм все еще не подходит, так как $$$\max(30 - 20, 0) + \max(30 - 25, 0) \gt 3$$$.
Таким образом, после первого запроса, фильм посмотрят $$$3$$$ человека.
