The Demiurge Slava created an one-dimensional world consisting of $$$n$$$ kingdoms on a line, where the $$$i$$$-th kingdom is located at position $$$i$$$ in the world.
All people believe in Slava, but perceive him differently, so the religions of different kingdoms may vary. Each unique religion will correspond to a unique non-negative integer. At the time of the world's creation, people's perception of Slava was the same, so all $$$n$$$ kingdoms had religion $$$0$$$.
Kingdoms can unite into alliances. Slava does not want disagreements to arise among kingdoms in an alliance, so all members of the alliance must share the same faith.
On the other hand, if kingdoms are so close in spirit, what prevents them from merging into one kingdom? Slava would prefer to avoid this, as a sufficiently strong kingdom might start wars with kingdoms of other religions.
At the same time, if the distance between allies becomes too great, it becomes difficult to maintain contact.
Realizing all this, Slava decided to introduce the following rules regarding alliances:
Consider an example: let $$$n = 6$$$, $$$k = 2$$$, and the religions of the kingdoms be $$$\{1, 2, 1, 3, 1, 3\}$$$. In this case, only the following alliances are possible:
Note that the alliance $$$\{1, 5\}$$$ is not possible, as the distance between the kingdoms is $$$4$$$, which is not equal to $$$k = 2$$$.
Sometimes kingdoms rethink their values or perceptions of the world and change their religion. This can lead to changes in the situation regarding possible alliances.
For example, if in the example above kingdom $$$6$$$ changes its faith from $$$3$$$ to $$$2$$$, the alliance $$$\{4, 6 \}$$$ will no longer be possible, as these kingdoms will now have different religions.
If after that kingdom $$$4$$$ also changes its religion to $$$2$$$, three alliances will become possible immediately:
Slava is a very busy demiurge, so he asks you, an angel-intern, to help him and report how many different alliances are possible in the described world after each change made by a kingdom to its religion.
The first line contains three numbers $$$n$$$, $$$k$$$, and $$$q$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 10^5$$$) — the number of kingdoms, the allowed distance for alliances, and the number of religion changes.
Next, $$$q$$$ lines contain two numbers $$$m_i$$$, $$$r_i$$$ ($$$1 \leq m_i \leq n$$$, $$$0 \leq r_i \leq 10^9$$$) — the number of the kingdom and its new religion. It is possible for the new religion to be the same as the old one (these are political matters not considered in this problem).
The initial religion for each of the $$$n$$$ kingdoms is $$$0$$$.
Output $$$q$$$ integers $$$a_i$$$ — the number of possible alliances in Slava's world after kingdom $$$m_i$$$ adopts religion $$$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
The test example corresponds to the example described in the statement — the first $$$6$$$ queries each change the religion from $$$0$$$, after which $$$2$$$ changes described in the example occur.
Let's consider the religions of the kingdoms and possible alliances after each religion change:
