Taja otrzymała łamigłówkę i wciąż nie ma pojęcia, jak ją rozwiązać.

Łamigłówka składa się z siatki $n \times n$, w której każdy wiersz i każda kolumna zawierają dokładnie jeden separator. Separator jest odcinkiem diagonalnym, który zaczyna się w lewym górnym rogu i kończy w prawym dolnym rogu komórki. Łamigłówka posiada przycisk startowy, który wystrzeliwuje kule w całkowitych momentach czasu z tub umieszczonych na krawędzi siatki. W każdej jednostce czasu kula przesuwa się do sąsiedniej komórki. Gdy kula zderzy się z separatorem, zmienia kierunek o $90^\circ$. Kula znika, jeśli przekroczy linię brzegową.

Aby rozwiązać łamigłówkę, należy obrócić niektóre separatory o $90^\circ$ wokół ich środków w taki sposób, aby żadne dwie kule nigdy nie zderzyły się wewnątrz siatki.

Dwie kule zderzają się, jeśli:

1. Znajdują się w tej samej komórce w tym samym momencie (jeśli komórka zawiera separator, obie kule muszą znajdować się po tej samej jego stronie).
2. Zderzyły się na granicy komórek (granica całej siatki również się liczy).

W tym zadaniu należy znaleźć dowolne rozwiązanie tej łamigłówki.

Wejście

Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 500$) — rozmiar siatki.

Druga linia zawiera $n$ liczb całkowitych ($1 \le c_i \le n$) — numer kolumny $i$-tego separatora, który znajduje się w wierszu o numerze $i$. Wszystkie numery kolumn są różne.

Trzecia linia zawiera pojedynczą liczbę całkowitą $m$ ($1 \le m \le 10^4$) — liczbę kul.

Każda z kolejnych $m$ linii zawiera 3 liczby całkowite $x_i, y_i, t_i$ ($0 \le t_i \le 10^8$), opisujące momenty wystrzelenia kul — w momencie $t_i$ kula pojawi się w komórce $(x_i, y_i)$, która ma wspólną krawędź z brzegiem siatki. Momenty podane są w kolejności niemalejącej względem $t_i$. Współrzędne $(x_i, y_i)$ mogą znajdować się w jednym z czterech następujących obszarów:

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

Gwarantuje się, że rozwiązanie zawsze istnieje.

Wyjście

Wyjście powinno zawierać pojedynczą linię złożoną z cyfr 0 i 1. $i$-ty symbol to 0, jeśli $i$-ty separator nie wymaga obrotu, a 1 — w przeciwnym razie.

Przykład

Wejście 1

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

Wyjście 1

011

Uwagi

Poniżej przedstawiono przykładowe położenia kul w czasie.