La \(30^a\) Olimpiada Mexicana de Informática (OMI) preparó un reto especial inspirado en la acústica del emblemático Teatro Degollado.

En el escenario hay un conjunto de \(n\) mariachis organizados en un arreglo \(a\) de tamaño \(n\). Cada posición del arreglo representa a un mariachi, y cada uno puede estar ausente (representado con \(-1\)) o presente tocando una nota musical con un cierto volumen (representado con un entero positivo).

El teatro tiene una resonancia característica descrita por un número entero \(k\). Al sonido final se le llama armonioso si se cumple que el volumen máximo entre todos los mariachis es exactamente igual a \(k\).

Te preguntas cuántas formas hay de asignar volúmenes a los mariachis ausentes de forma que su sonido sea armonioso, a lo cual responderás de la siguiente forma:

• Si hay una cantidad par de asignaciones válidas, imprime \(0\).
• Si hay una cantidad impar de asignaciones válidas, imprime \(1\).

Dos formas de asignar volúmenes se consideran diferentes si existe al menos un mariachi ausente que toca una nota distinta en una de las formas. Una sola operación como la anterior se le hace insuficiente al COMI (Consejo Operador de Música Innovadora), por lo que te piden responder de la forma descrita en el párrafo anterior después de cada una de \(q\) operaciones. Las operaciones (escritas en líneas separadas) son de la forma

\(i\) \(x\)

y consisten en actualizar la posición \(i\) con el valor \(x\) (puede ser \(-1\) si el mariachi está ausente, o un entero positivo si toca con ese volumen).

Entrada

• La primera línea contiene tres enteros \(n, q\) y \(k\).
• La segunda línea contiene \(n\) enteros \(a_1, a_2, . . . , a_n\), representando el arreglo inicial de notas que tocan los mariachis.

A continuación siguen \(q\) operaciones, cada una con el formato \(i\) \(x\) con \((1 \leq i \leq n)\) y \(x = -1\) o \(1 \leq x \leq 10^6\). Esto indica que debes asignarle el valor \(x\) a la posición \(i\). Imprime la respuesta para el arreglo después de cada operación.

Salida

Por cada operación, imprime una línea con un entero:

• \(0\) si el número de formas de llenar los lugares vacíos para que el máximo de todos los volúmenes sea exactamente \(k\) es par.
• \(1\) si el número de formas de llenar los lugares vacíos para que el máximo de todos los volúmenes sea exactamente \(k\) es impar.

Ejemplo

Entrada

5 3 7
2 -1 6 1 6
1 3
2 1
3 7

Salida

1
0
1

• Después de la primera actualización, el arreglo es \([3, -1, 6, 1, 6]\). Existe una única asignación válida, que es el arreglo \([3, 7, 6, 1, 6]\).
• Después de la segunda actualización, el arreglo es \([3, 1, 6, 1, 6]\), y como no hay ningún mariachi ausente, no existe ninguna asignación posible.
• Después de la tercera actualización, el arreglo es \([3, 1, 7, 1, 6]\). Por lo que existe una unicá asignación válida, que es no hacer nada.

Consideraciones

• \(1 \leq n \leq 10^5\).
• \(0 \leq q \leq 10^5\).
• \(1 \leq k \leq 10^6\).
• \(a_i = -1\) o \(1 \leq a_i \leq 10^6\) \((1 \leq i \leq n)\).

Subtareas

• Subtarea 1 (15 puntos): \(k = 1\)
• Subtarea 2 (15 puntos): \(k = 10^6\)
• Subtarea 3 (15 puntos): \(Q,N \leq 10^3\)
• Subtarea 4 (25 puntos): Ninguna actualización modificará a un valor del arreglo distinto de \(-1\). Además, un valor positivo ya existente nunca se volverá \(-1\) con una actualización.
• Subtarea 5 (30 puntos): Sin restricciones adicionales.