409456: GYM103566 D Королевства и союзы

D. Королевства и союзыограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Демиург Слава создал одномерный мир из $$$n$$$ королевств на прямой, причем $$$i$$$-е королевство находится на позиции $$$i$$$ в мире.

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

Королевства могут объединяться в союзы. Слава не хочет, чтобы у королевств в союзе возникали разногласия, поэтому у всех в союзе должно быть одинаковое вероисповедание.

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

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

Осознав всё это, Слава решил ввести следующие правила относительно союзов:

1. союз состоит минимум из $$$2$$$ королевств;
2. все королевства в союзе имеют одну и ту же религию;
3. соседние в союзе королевства находятся строго на расстоянии $$$k$$$, ни больше ни меньше. Расстояние между королевствами $$$i$$$ и $$$j$$$ равно $$$|i - j|$$$.

Рассмотрим пример: пусть $$$n = 6$$$, $$$k = 2$$$ и вероисповедания королевств равны $$$\{1, 2, 1, 3, 1, 3\}$$$. В таком случае возможны только следующие союзы:

1. $$$\{1, 3 \}$$$
2. $$$\{1, 3, 5 \}$$$
3. $$$\{3, 5 \}$$$
4. $$$\{4, 6 \}$$$

Обратите внимание, что союз $$$\{1, 5\}$$$ невозможен, так как расстояние между королевствами равно $$$4$$$, что не равно $$$k = 2$$$.

Иногда королевства переосмысливают свои ценности или восприятие мира и меняют религию. Это может приводить к изменению ситуации с возможными союзами.

К примеру, если в описанном выше примере королевство $$$6$$$ изменит свою веру с $$$3$$$ на $$$2$$$, то пропадёт возможность союза $$$\{4, 6 \}$$$, так как теперь у этих королевств будут различные религии.

Если же после этого королевство $$$4$$$ тоже изменит религию на $$$2$$$, то станут возможными сразу три союза:

1. $$$\{2, 4 \}$$$
2. $$$\{2, 4, 6 \}$$$
3. $$$\{4, 6 \}$$$

Слава  — очень занятой демиург, поэтому просит вас  — ангела-стажёра  — помочь ему и после каждого изменения каким-либо королевством своей религии сообщать, сколько различных союзов возможно в данный момент в описанном мире.

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

В первой строке записано три числа $$$n$$$, $$$k$$$ и $$$q$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 10^5$$$)  — количество королевств, разрешенное для союза расстояние и количество изменений вероисповедания.

Далее в $$$q$$$ строках вводятся по два числа $$$m_i$$$, $$$r_i$$$ ($$$1 \leq m_i \leq n$$$, $$$0 \leq r_i \leq 10^9$$$)  — номер королевства и его новое вероисповедание. Возможны ситуации, когда новое вероисповедание совпадает со старым (это уже вопросы политики, не рассматриваемые в рамках данной задачи).

Начальная религия для каждого из $$$n$$$ королевств равна $$$0$$$.

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

Выведите $$$q$$$ целых чисел $$$a_i$$$  — количество возможных союзов в мире Славы после принятия королевством $$$m_i$$$ религии $$$r_i$$$.

ПримерВходные данные

6 2 8
1 1
3 1
2 2
6 3
5 1
4 3
6 2
4 2

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

4
4
2
1
3
4
3
6

Примечание

Тестовый пример соответствует описанному в условии примеру  — первые $$$6$$$ запросов каждое королевство изменяет свою религию с $$$0$$$, после чего происходят $$$2$$$ описанных в примере изменения.

Рассмотрим вероисповедания королевств и возможные союзы после каждого изменения религии:

1. $$$\{1,0,0,0,0,0\}$$$:
   • $$$\{3,5\}$$$
   • $$$\{2,4\}$$$
   • $$$\{2,4,6\}$$$
   • $$$\{4,6\}$$$

2. $$$\{1,0,1,0,0,0\}$$$:
   • $$$\{1,3\}$$$
   • $$$\{2,4\}$$$
   • $$$\{2,4,6\}$$$
   • $$$\{4,6\}$$$
3. $$$\{1,2,1,0,0,0\}$$$:
   • $$$\{1,3\}$$$
   • $$$\{4,6\}$$$
4. $$$\{1,2,1,0,0,3\}$$$:
   • $$$\{1,3\}$$$
5. $$$\{1,2,1,0,1,3\}$$$:
   • $$$\{1,3\}$$$
   • $$$\{1,3,5\}$$$
   • $$$\{3,5\}$$$
6. $$$\{1,2,1,3,1,3\}$$$:
   • $$$\{1,3\}$$$
   • $$$\{1,3,5\}$$$
   • $$$\{3,5\}$$$
   • $$$\{4,6\}$$$
7. $$$\{1,2,1,3,1,2\}$$$:
   • $$$\{1,3\}$$$
   • $$$\{1,3,5\}$$$
   • $$$\{3,5\}$$$
8. $$$\{1,2,1,2,1,2\}$$$:
   • $$$\{1,3\}$$$
   • $$$\{1,3,5\}$$$
   • $$$\{2,4\}$$$
   • $$$\{2,4,6\}$$$
   • $$$\{3,5\}$$$
   • $$$\{4,6\}$$$