Una vez que le han regalado un rompecabezas a Taja, ella todavía no tiene idea de cómo resolverlo.

El rompecabezas es una cuadrícula de $n \times n$, donde cada fila y cada columna contiene exactamente un separador, el cual es un segmento diagonal que comienza en la esquina superior izquierda y termina en la esquina inferior derecha. El rompecabezas tiene un botón de lanzamiento que lanza las bolas en momentos de tiempo enteros desde tubos situados en el borde de la cuadrícula. En cada unidad de tiempo, una bola se mueve a una celda adyacente. Cuando una bola choca con un separador, cambia su dirección $90^\circ$. Una bola desaparece si cruza la línea del borde.

Para resolver el rompecabezas, uno debe rotar algunos separadores $90^\circ$ alrededor de sus centros, de tal manera que ninguna de las dos bolas choque nunca dentro de la cuadrícula.

Dos bolas chocan si:

1. Están en la misma celda en el mismo momento (si la celda contiene un separador, entonces ambas bolas deben estar en el mismo lado).
2. Chocaron en el límite de las celdas (el límite de toda la cuadrícula también cuenta).

En este problema, usted debe encontrar cualquier solución para este rompecabezas.

Entrada

La primera línea de la entrada contiene un único entero $n$ ($1 \le n \le 500$) — el tamaño de la cuadrícula.

La segunda línea contiene $n$ enteros ($1 \le c_i \le n$) — el número de columna del $i$-ésimo separador, el cual tiene a $i$ como número de fila. Todos los números de columna son diferentes.

La tercera línea contiene un único entero $m$ ($1 \le m \le 10^4$) — el número de bolas.

Cada una de las siguientes $m$ líneas contiene 3 enteros $x_i, y_i, t_i$ ($0 \le t_i \le 10^8$), que describen los momentos de lanzamiento de las bolas — en el momento $t_i$ una bola aparecerá en la celda $(x_i, y_i)$, la cual comparte un lado común con el borde de la cuadrícula. Los momentos se dan en orden no decreciente de $t_i$. Las coordenadas $(x_i, y_i)$ pueden estar en una de las cuatro áreas siguientes:

1. $x_i = 0, 1 \le y_i \le n$;
2. $1 \le x_i \le n, y_i = 0$;
3. $x_i = n + 1, 1 \le y_i \le n$;
4. $1 \le x_i \le n, y_i = n + 1$.

Se garantiza que siempre existe una solución.

Salida

La salida debe contener una única línea de 0 y 1. El $i$-ésimo símbolo es 0 si el $i$-ésimo separador no requiere rotación, y 1 en caso contrario.

Ejemplos

Entrada 1

3
2 1 3
6
2 0 0
3 0 1
1 0 2
0 2 2
4 3 3
0 1 3

Salida 1

011

Nota

A continuación se muestran posiciones de muestra de las bolas a lo largo del tiempo.

Figura 1. Representación del rompecabezas de cuadrícula con separadores y tubos de lanzamiento.