Visto desde el espacio, el mapa de IslaGrande tiene la forma de una cuadrícula cuadrada con ~L~ filas y ~L~ columnas.

Las filas y columnas están numeradas del ~1~ al ~L~. En cada una de las ~L * L~ celdas hay un farol. Inicialmente, el que está en la posición ~1, 1~ está encendido y todos siguen la regla: cada faro tiene faros vecinos (en la fila y la columna, como máximo, son ~4~) en el estado opuesto a su estado.

Después del ciclón Irma, sucedieron cosas extrañas: un rayo cayó uno tras otro, y otro y afectó el estado de algunos faros.

Hay tres tipos de rayos:

• Rayo de tipo ~1~. Para esto, indica la fila en la que golpea y afecta la condición de los faros en la fila respectiva y en las filas con un número de orden más alto. Específicamente, todos los faros en estas filas cambian instantáneamente su estado.

• Rayo de tipo ~2~. Para esto, indique un número que represente la columna en la que incide y afecta la condición de los faros en la columna respectiva y en las columnas con un número de orden superior. Específicamente, todos los faros de estas columnas cambian instantáneamente su estado.

• Rayo de tipo ~3~. Para esto, indique la fila y luego la columna de un elemento de cuadrícula. Todos los faros en el mismo paralelo a la diagonal secundaria con el elemento especificado y en los paralelos diagonales secundarios debajo cambian su condición.

Al cambiar el estado de un faro, queremos decir que se ilumina si está apagado y se apaga si está encendido.

Tarea

Los datos del rayo se dan, en el orden en que actúan. Se solicita que al final de la tormenta indique el estado de ciertos faros, ubicados en las coordenadas especificadas en la isla

Especificación de la Entrada

La primera fila de la entrada estándar contiene un número natural L, con el significado anterior. En la segunda fila hay un número natural R, que representa el número de rayos. Las siguientes R filas contienen datos sobre un rayo, en el orden en que aparecen. El primer número en cada fila es el tipo de rayo (~1~ o ~2~ o ~3~). Si este número es ~1~ o ~2~, hay un espacio y un número más en esta fila. Esto representa la fila en la que cae el rayo (si la fila comienza en ~1~), respectivamente, la columna en la que cae el rayo (si la fila respectiva tiene al principio ~2~). En el caso del rayo de tipo ~3~, hay dos números en esa fila, que representan la fila y la columna del elemento en la isla donde cae el rayo, separados por espacio.

La siguiente fila contiene un número Q. En las siguientes Q filas hay dos números (separados por espacio) que representan la fila y la columna de un faro en la isla para el que se desea encontrar el estado después de la tormenta.

Especificación de la Salida

La misma contiene en una fila, separada por un espacio, Q números, que representan los resultados de la consulta en el orden en que aparecen en la entrada. Si se enciende el faro correspondiente, se escribirá el valor ~1~ y, si está apagado, se escribirá el valor ~0~. Tenga en cuenta el final que no quede un espacio demás.

Restricciones y especificaciones

• ~2 \le L \le 2~ mil millones
• ~1 \le R \le 1000~
• Se garantiza que cuando se especifica un rayo, la fila comienza con ~1~, ~2~ o ~3~ y los otros valores en las filas respectivas están entre ~1~ y ~L~ inclusive.
• ~1 \le Q \le 100000~
• Se garantiza que para cada faro cuyo estado debe ubicarse la fila y la columna se encuentren entre ~1~ y ~L~ inclusive.
• Para ~24~ % de los puntos, ~L \le 100, R \le 100~ y solo aparecen los rayos del tipo ~1~;
• Para otros ~18~ % de los puntos, ~L \le 100~, ~R \le 100~;
• Para otros ~12~ % de los puntos, ~L \le 10,000~ y solo aparecen los rayos del tipo ~1~;
• Para otros ~8~ % de los puntos, ~L \le 10,000~;
• Para otros ~13~ % de los puntos, ~L \le 1000000~;
• Para los ~25~ % de los puntos restantes no hay restricciones adicionales.

Ejemplos de Entrada

4
3
1 2
3 3 1
2 3
5
1 1
2 4
3 2
4 2
4 4

Ejemplo de Salida

1 0 0 1 0

Explicación

Inicialmente, la condición de los faroles de la isla se puede representar de la siguiente manera:

1 0 1 0

0 1 0 1

1 0 1 0

0 1 0 1

Después de caer el primer rayo, la condición de los faroles se vuelve

1 0 1 0

1 0 1 0

0 1 0 1

1 0 1 0

Después de caer el segundo rayo, la condición de los faroles se vuelve

1 0 0 1

1 1 0 1

1 0 1 0

0 1 0 1

Después de caer el tercer rayo, los faroles se convierten en

1 0 1 0

1 1 1 0

1 0 0 1

0 1 1 0