E. Summer School
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Начался набор на новую смену Школы олимпиадного программирования. В этом году произошло изменение в образовательных параллелях. В школе будет $$$n$$$ параллелей для уровней от $$$0$$$ до $$$n - 1$$$. В каждой параллели есть $$$k$$$ мест для поступающих школьников.

Также по результатам участия в олимпиадах и тренировок каждый школьник получил оценку от искусственного интеллекта — целое число от $$$0$$$ до $$$n - 1$$$.

Школьнику с уровнем $$$L$$$ будет полезным обучаться в параллели $$$x$$$, если уровень школьника отличается от уровня параллели не более чем на $$$d + L \cdot \frac{p}{100}$$$, то есть $$$|x - L| \le d + L \cdot \frac{p}{100}$$$.

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

По случайному стечению обстоятельств каждый день происходит одно из двух:

  1. + L v — $$$v$$$ школьников уровня $$$L$$$ зарегистрировались;
  2. - L v — $$$v$$$ школьников уровня $$$L$$$ отказались от участия.

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

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

В первой строке заданы целые числа $$$n$$$, $$$k$$$, $$$d$$$ и $$$p$$$ — число параллелей, число мест в каждой параллели, параметры для определения полезности параллели, соответственно ($$$1 \le n \le 5 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$, $$$0 \le d \le n$$$, $$$0 \le p \le 100$$$).

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

В следующих $$$m$$$ строках заданы события, которые происходят каждый день. В каждой строке задано либо + L v, либо - L v, где $$$L$$$ — уровень школьника, а $$$v$$$ — число таких заявок ($$$0 \le L \lt n$$$, $$$1 \le v \le 10^9$$$).

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

В $$$m$$$ строках выведите по целому числу, сколько школьников можно зачислить, чтобы всем зачисленным смена оказалась полезной.

Система оценки

Назовем $$$C$$$ — максимальное число заявок одного уровня, которые были в какой-то момент зарегистрированы в системе.

ПодзадачаБаллыОграничения
110$$$n \le 5$$$, $$$m \le 10$$$, $$$C \le 4$$$
210$$$n \le 30$$$, $$$m \le 100$$$, $$$C \le 30$$$
310$$$n, m \le 100$$$, $$$C \le 10^6$$$
410$$$n, m \le 10^5$$$, $$$d = 0$$$
510$$$n, m \le 10^5$$$, $$$d \le 1$$$
610$$$n, m \le 10^5$$$, $$$p = 0$$$
710$$$n, m \le 10^5$$$, $$$v = 1$$$
810$$$n, m \le 10^5$$$, только запросы вида '+'
910$$$n, m \le 10^5$$$
1010Без дополнительных ограничений
Примеры
Входные данные
5 2 1 25
5
+ 4 7
- 4 3
+ 2 5
+ 3 5
- 3 2
Выходные данные
6
4
8
8
8
Входные данные
5 2 1 1
6
+ 0 4
+ 1 3
- 0 2
+ 3 7
+ 4 1
- 3 6
Выходные данные
4
6
5
10
10
7
Примечание

В первом примере школьники уровня 4 могут поступить в параллель 2, 3 и 4, поэтому после первого дня 6 школьников из 7 могут с пользой для себя поступить в смену.

Во втором примере все школьники могут поступить только в параллели такого же уровня, либо отличающиеся по уровню на единицу.