Love is all a matter of timing. It's no good meeting the right person too soon or too late...

Descripción

Es 2046 y el mundo es un caos, el amor ya no prevalece y las calles de Hong Kong están rodeadas de infinitos cables de luz atados a postes para proveer de energía a los miles de edificios para las millones de personas que existen en este año. Como hay tantos cables, y los robots se confunden para dar mantenimiento a estos, ha crecido la cantidad de empleos relacionados a su cuidado y tú trabajas de esto.

En el 2046 las palomas todavía se suben a los postes y cables de luz para descansar (sí, milagrosamente aún existen algunos animales). En tu zona de trabajo hay \(N\) filas de cables de luz que están numerados del \(1\) al \(N\), en cada fila, al inicio, están durmiendo \(M\) palomas, pero como los niños de esa época son malvados, disfrutan lanzarles piedras para ver cómo se despiertan y se mueven. Cada que un niño va a lanzar una piedra hace lo siguiente:

• Selecciona una fila entre \(1\) y \(N\).
• Como las palomas duermen juntitas, selecciona alguna entre la primera y la última que haya en esa fila.
• Lanza la piedra a la paloma que seleccionó, pero como se espantan antes de que llegue a impactarla, todas las palomas que están a la derecha se mueven al cable de arriba (incluyendo a quien le lanzó la piedra); de igual forma, todas las palomas que están a la izquierda de donde la lanzó, se mueven al cable de abajo.

Si se lanza una piedra a la primer fila, como ya no hay más filas superiores, las palomas que vayan hacia arriba se van volando a otro lugar de Hong Kong y ya nunca regresan a ese lugar. De igual forma, si se lanza una piedra a la última fila, las palomas que vayan hacia abajo, tampoco regresan a ningún cable. Si por error el niño tira una piedra en donde no hay ninguna paloma, este la lanzará en donde sea.

Problema

Dado que hay muchos niños con ganas de lanzar piedras y los cables tienen una capacidad máxima de palomas que pueden estar sobre ellos, después de cada lanzamiento de un niño, debes reportar cuál es la máxima cantidad de palomas que hay en una sola fila.

Entrada

La primera línea consiste en tres enteros: \(N\), \(M\), \(Q\). La cantidad de filas de cables que hay, la cantidad de palomas durmiendo en cada cable al inicio y la cantidad de niños que lanzarán una piedra.

En las siguientes \(Q\) líneas habrá dos enteros: \(F\), \(P\). La fila en donde el niño lanzó la piedra y la posición de la paloma en donde aventó la piedra.

Salida

Se deberán imprimir \(Q\) líneas, en cada línea se debe reportar la máxima cantidad de palomas que hay en una sola fila después del lanzamiento del \(q-ésimo\) niño.

Ejemplos

Entrada

10 5 3
3 3
6 5
10 1

Salida

8
9
10

Explicación:

• Al inicio hay 5 palomas en cada cable: \([5, 5, 5, 5, 5, 5, 5, 5, 5, 5]\).
• Después del primer lanzamiento, la cantidad de palomas que hay en cada cable son: \([5, 8, 0, 7, 5, 5, 5, 5, 5, 5]\).
• Después del segundo lanzamiento, la cantidad de palomas que hay en cada cable son: \([5, 8, 0, 7, 6, 0, 9, 5, 5, 5]\).
• Después del tercer lanzamiento, la cantidad de palomas que hay en cada cable son: \([5, 8, 0, 7, 6, 0, 9, 5, 10, 0]\).

Entrada

5 4 3
1 1
1 10
5 4

Salida

4
4
5

Explicación:

• Al inicio hay 4 palomas en cada cable: \([4, 4, 4, 4, 4]\).
• Después del primer lanzamiento, la cantidad de palomas que hay en cada cable son: \([0, 4, 4, 4, 4]\).
• Después del segundo lanzamiento, la cantidad de palomas que hay en cada cable son: \([0, 4, 4, 4, 4]\).
• Después del tercer lanzamiento, la cantidad de palomas que hay en cada cable son: \([0, 4, 4, 5, 0]\).

Consideraciones

• \(1 \leq N, M \leq 10^9\).
• \(1 \leq Q \leq 10^5\).
• \(1 \leq F \leq N\).
• Si en la fila \(F\) hay palomas, entonces \(P\) estará entre \(1\) y la cantidad de palomas que haya en esa fila.
• Si en la fila \(F\) no hay palomas, entonces \(0 \leq P \leq 10^{18}\).