Начался набор на новую смену Школы олимпиадного программирования. В этом году произошло изменение в образовательных параллелях. В школе будет $$$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}$$$.
Каждый день в систему регистрации приходят заявки: школьники либо регистрируются, либо отказываются от участия. Чтобы помочь спланировать школьникам свое лето, организаторы решили дописать в систему программу, которая определяет, скольки школьникам участие будет полезным.
По случайному стечению обстоятельств каждый день происходит одно из двух:
Вам требуется написать программу, которая после каждого дня определит, какое максимальное число школьников можно зачислить, чтобы им смена оказалась полезной.
В первой строке заданы целые числа $$$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$$$ — максимальное число заявок одного уровня, которые были в какой-то момент зарегистрированы в системе.
| Подзадача | Баллы | Ограничения |
| 1 | 10 | $$$n \le 5$$$, $$$m \le 10$$$, $$$C \le 4$$$ |
| 2 | 10 | $$$n \le 30$$$, $$$m \le 100$$$, $$$C \le 30$$$ |
| 3 | 10 | $$$n, m \le 100$$$, $$$C \le 10^6$$$ |
| 4 | 10 | $$$n, m \le 10^5$$$, $$$d = 0$$$ |
| 5 | 10 | $$$n, m \le 10^5$$$, $$$d \le 1$$$ |
| 6 | 10 | $$$n, m \le 10^5$$$, $$$p = 0$$$ |
| 7 | 10 | $$$n, m \le 10^5$$$, $$$v = 1$$$ |
| 8 | 10 | $$$n, m \le 10^5$$$, только запросы вида '+' |
| 9 | 10 | $$$n, m \le 10^5$$$ |
| 10 | 10 | Без дополнительных ограничений |
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 могут с пользой для себя поступить в смену.
Во втором примере все школьники могут поступить только в параллели такого же уровня, либо отличающиеся по уровню на единицу.
