El juego de la escalera es popular en Corea, así como en China y Japón. Wikipedia dice: «En coreano se conoce como Sadaritagi (사다리타기, literalmente “subir la escalera”), en japonés como Amidakuji (阿弥陀籤, “lotería de Amida”) y en chino como Guijiaotu (鬼腳圖, literalmente “diagrama de patas de fantasma”)».

El diagrama del juego consta de $n$ líneas verticales con segmentos horizontales que conectan dos líneas verticales adyacentes. Los segmentos horizontales se llaman peldaños. Cada línea vertical tiene un punto inicial (superior) y uno final (inferior). La regla básica es sencilla:

• Comienza en el punto inicial de cada línea vertical y baja por ella. Al encontrar un peldaño, síguelo hasta la línea vertical adyacente y continúa bajando hasta llegar al final de una línea vertical.

Las líneas verticales están numeradas del $1$ al $n$ de izquierda a derecha. Es bien sabido que el resultado es una permutación de $[1,2,\ldots,n]$. Por ejemplo, con el diagrama siguiente, de 4 líneas verticales y 5 peldaños, el resultado de izquierda a derecha es $[2,3,4,1]$.

Sin embargo, algunos peldaños son redundantes: el mismo resultado $[2,3,4,1]$ se puede obtener con menos peldaños. Como en la figura siguiente, bastan tres peldaños si se excluyen el superior y el inferior. Queremos determinar el mínimo número de segmentos horizontales (peldaños) necesario para lograr el mismo resultado. Si es necesario, se pueden dibujar peldaños nuevos distintos de los dados.

Se dan $q$ consultas, cada una de las cuales añade un peldaño nuevo o elimina uno existente. Escribe un programa que imprima el mínimo número de peldaños necesario para lograr el mismo resultado que la estructura obtenida después de procesar cada consulta. Las consultas son acumulativas: cada una se aplica a la estructura resultante de las anteriores.

Entrada

Tu programa debe leer de la entrada estándar. La primera línea contiene tres enteros separados por espacios: $n$, el número de líneas verticales; $m$, el número inicial de peldaños; y $q$, el número de consultas, con $2\le n\le100000$, $1\le m\le100000$ y $1\le q\le100000$.

Cada una de las siguientes $m$ líneas contiene dos enteros positivos $h,a$, que representan un peldaño de altura $h$ entre las líneas verticales $a$ y $a+1$ ($1\le a\le n-1$). Las líneas están ordenadas de izquierda a derecha, y la altura se numera de arriba abajo empezando por $1$. La altura no supera $10^9$.

Las siguientes $q$ líneas contienen las consultas. Cada una tiene la forma $\mathrm{A}\ h\ a$ o $\mathrm{D}\ h\ a$, donde $1\le h\le10^9$, $1\le a\le n-1$.

• $\mathrm{A}\ h\ a$: añade un peldaño de altura $h$ entre las líneas verticales $a$ y $a+1$.

• $\mathrm{D}\ h\ a$: elimina el peldaño de altura $h$ entre las líneas verticales $a$ y $a+1$.

Puedes suponer que no hay operaciones contradictorias: no se añaden peldaños existentes ni se eliminan peldaños inexistentes. También puedes suponer que ningún par de peldaños comparte un extremo a la misma altura y en la misma línea vertical.

Salida

Tu programa debe escribir en la salida estándar. La salida consta de $q$ líneas, cada una con el mínimo número de peldaños necesario para obtener el mismo resultado para una consulta, en el orden de entrada.

A continuación se muestran entradas y salidas de ejemplo para dos casos de prueba.

Ejemplos

Entrada 1

4 4 3
3 1
2 2
5 2
6 3
A 7 1
A 4 3
D 3 1

Salida 1

3
6
3

Nota

El primer ejemplo da la estructura inicial siguiente. El resultado es $[3,2,4,1]$.

Al aplicar la primera consulta A 7 1 en la figura siguiente, la estructura cambia y el resultado pasa a ser $[2,3,4,1]$.

De los cinco peldaños, bastan tres, sin el superior ni el inferior, para conseguir el mismo resultado $[2,3,4,1]$, como en la figura siguiente. Por tanto, la respuesta a la primera consulta es $3$.

Tras procesar la segunda consulta A 4 3, la estructura cambia como muestra la figura siguiente. El número de peldaños no se puede reducir más. La respuesta a la segunda consulta es $6$.

Al aplicar la tercera consulta D 3 1, la estructura cambia como muestra la figura siguiente.

La estructura siguiente, con tres peldaños, garantiza el mismo resultado, así que la respuesta a la tercera consulta es $3$.

Entrada 2

4 5 5
3 1
2 2
5 2
6 3
7 1
D 6 3
D 7 1
D 5 2
D 3 1
D 2 2

Salida 2

2
3
2
1
0