Une fois qu'un puzzle a été offert à Taja, elle n'a toujours aucune idée de la façon de le résoudre.

Le puzzle est une grille $n \times n$, où chaque ligne et chaque colonne contient exactement un séparateur, qui est un segment diagonal commençant dans le coin supérieur gauche et se terminant dans le coin inférieur droit. Le puzzle possède un bouton de lancement qui lance les billes à des moments entiers depuis des tubes positionnés sur la bordure de la grille. À chaque instant, une bille se déplace vers une cellule adjacente. Lorsqu'une bille entre en collision avec un séparateur, elle change de direction de $90^\circ$. Une bille disparaît si elle franchit la ligne de bordure.

Pour résoudre un puzzle, il faut faire pivoter certains séparateurs de $90^\circ$ autour de leur centre, de telle sorte qu'aucune bille ne puisse jamais entrer en collision à l'intérieur de la grille.

Deux billes entrent en collision si :

1. Elles se trouvent dans la même cellule au même moment (si la cellule contient un séparateur, alors les deux billes doivent se trouver du même côté).
2. Elles sont entrées en collision à la frontière des cellules (la bordure de toute la grille compte également).

Dans ce problème, vous devez trouver n'importe quelle solution à ce puzzle.

Entrée

La première ligne de l'entrée contient un entier unique $n$ ($1 \le n \le 500$) — la taille de la grille.

La deuxième ligne contient $n$ entiers ($1 \le c_i \le n$) — le numéro de colonne du $i$-ième séparateur, qui a $i$ comme numéro de ligne. Tous les numéros de colonne sont distincts.

La troisième ligne contient un entier unique $m$ ($1 \le m \le 10^4$) — le nombre de billes.

Chacune des $m$ lignes suivantes contient 3 entiers $x_i, y_i, t_i$ ($0 \le t_i \le 10^8$), décrivant les moments de lancement des billes — au moment $t_i$, une bille apparaîtra dans la cellule $(x_i, y_i)$, qui partage un côté commun avec la bordure de la grille. Les moments sont donnés dans l'ordre non décroissant de $t_i$. Les coordonnées $(x_i, y_i)$ peuvent se trouver dans l'une des quatre zones suivantes :

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$.

Il est garanti qu'une solution existe toujours.

Sortie

La sortie doit contenir une seule ligne composée de 0 et de 1. Le $i$-ième symbole est 0 si le $i$-ième séparateur ne nécessite pas de rotation, et 1 sinon.

Exemples

Entrée 1

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

Sortie 1

011

Remarque

Les positions des billes au cours du temps sont illustrées ci-dessous.

Figure 1. Illustration of the puzzle grid and marble launchers.