M. Magic Marbles
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You may know Wizard's Chess, which is a magical version of chess, but there are more magical games in the wizarding world. Another one you may recognize is Magic Marbles, which is similar to the muggle game Marble Temple. In this game, you are given a chain of differently coloured marbles $$$m$$$, which you need to destroy. To do this, you can add additional marbles to the chain. This may sound counterproductive, but if there ever is a run of at least $$$k$$$ consecutive marbles that are of the same colour, then all of these marbles magically disappear instantly. The resulting gap is closed by moving the remaining marbles closer together, which can lead to new runs that then again disappear.

The initial state of the first sample. The first marble will be added between the second yellow marble and the first blue marble. Since this results in a run of three blue marbles, all of them instantly disappear.

This year there is a great Magic Marbles tournament in Hogwarts. However, you fear that some magicians are not as sincere as you and may try to cheat in this magic tournament. Therefore, you decided to simulate the game without magic.

Input

The input consists of:

  • One line with three integers $$$n$$$, $$$k$$$, $$$q$$$ $$$(1\leq n,q\leq2\cdot10^5, 2\leq k\leq4\cdot10^5)$$$, the initial length of the marble chain $$$m$$$, the minimal run length where marbles disappear, and the number of marbles that will be added during the game.
  • One line with $$$n$$$ space-separated integers $$$m_i$$$ $$$(1\leq m_i\leq10^6)$$$, where $$$m_i$$$ is the colour of the $$$i$$$-th marble of the initial chain $$$m$$$. It is guaranteed that each run of marbles of the same colour has length less than $$$k$$$.
  • $$$q$$$ lines, each containing two integers $$$p_x$$$ and $$$m_x$$$ $$$(0\leq p_x \leq |m|, 1\leq m_x\leq10^6)$$$, the position where the next marble will be inserted and the colour of the marble that is inserted. $$$|m|$$$ denotes the current length of the marble chain. If the position $$$p_x$$$ is $$$0$$$, the marble will be added in front of the currently first marble. Otherwise, the marble will be added after the $$$p_x$$$-th marble.
Output

For each of the $$$q$$$ insertions of a new marble, output a single integer $$$|m|$$$, the length of the marble chain after that insertion and any deletions that were caused by it.

Examples
Input
7 3 2
1 2 2 1 3 3 1
4 3
3 2
Output
5
0
Input
5 2 3
1 2 1 2 3
0 1
1 1
0 3
Output
4
1
0