Таджа получила в подарок головоломку, но до сих пор не знает, как её решить.

Головоломка представляет собой сетку $n \times n$, в каждой строке и каждом столбце которой находится ровно один разделитель. Разделитель — это диагональный отрезок, который начинается в верхнем левом углу и заканчивается в нижнем правом углу ячейки. У головоломки есть кнопка запуска, которая запускает шары в целочисленные моменты времени из трубок, расположенных на границе сетки. За один момент времени шар перемещается в соседнюю ячейку. При столкновении с разделителем шар меняет направление на $90^\circ$. Шар исчезает, если пересекает границу сетки.

Чтобы решить головоломку, нужно повернуть некоторые разделители на $90^\circ$ вокруг их центров так, чтобы никакие два шара никогда не столкнулись внутри сетки.

Два шара сталкиваются, если: 1. Они находятся в одной и той же ячейке в один и тот же момент времени (если ячейка содержит разделитель, то оба шара должны находиться с одной и той же его стороны). 2. Они столкнулись на границе ячеек (граница всей сетки также учитывается).

В этой задаче вам нужно найти любое решение этой головоломки.

Входные данные

Первая строка входных данных содержит единственное целое число $n$ ($1 \le n \le 500$) — размер сетки.

Вторая строка содержит $n$ целых чисел ($1 \le c_i \le n$) — номер столбца $i$-го разделителя, который находится в строке с номером $i$. Все номера столбцов различны.

Третья строка содержит единственное целое число $m$ ($1 \le m \le 10^4$) — количество шаров.

Каждая из следующих $m$ строк содержит 3 целых числа $x_i, y_i, t_i$ ($0 \le t_i \le 10^8$), описывающих моменты запуска шаров — в момент времени $t_i$ шар появится в ячейке $(x_i, y_i)$, которая имеет общую сторону с границей сетки. Моменты времени даны в неубывающем порядке $t_i$. Координаты $(x_i, y_i)$ могут находиться в одной из четырех следующих областей: 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$.

Гарантируется, что решение всегда существует.

Выходные данные

Выведите одну строку, состоящую из $0$ и $1$. $i$-й символ равен $0$, если $i$-й разделитель не требует поворота, и $1$ — в противном случае.

Примеры

Входные данные 1

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

Выходные данные 1

011

Примечание

Ниже показаны примеры положений шаров с течением времени.