Taja được tặng một câu đố và cô ấy vẫn chưa biết cách giải nó.

Câu đố là một lưới $n \times n$, trong đó mỗi hàng và mỗi cột chứa chính xác một bộ tách (separator). Bộ tách là một đoạn thẳng chéo bắt đầu từ góc trên bên trái và kết thúc ở góc dưới bên phải của ô. Câu đố có một nút khởi động, nút này phóng các quả bóng tại các thời điểm nguyên từ các ống được đặt ở biên của lưới. Tại mỗi thời điểm, một quả bóng di chuyển sang ô liền kề. Khi một quả bóng va chạm với một bộ tách, nó sẽ đổi hướng $90^\circ$. Một quả bóng sẽ biến mất nếu nó vượt qua đường biên của lưới.

Để giải câu đố, cần xoay một số bộ tách $90^\circ$ quanh tâm của chúng, sao cho không có hai quả bóng nào va chạm với nhau bên trong lưới.

Hai quả bóng va chạm nếu: 1. Chúng ở cùng một ô tại cùng một thời điểm (nếu ô đó chứa bộ tách, thì cả hai quả bóng phải ở cùng một phía của bộ tách). 2. Chúng va chạm tại biên của các ô (biên của toàn bộ lưới cũng được tính).

Trong bài toán này, bạn cần tìm bất kỳ lời giải nào cho câu đố.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $n$ ($1 \le n \le 500$) — kích thước lưới.

Dòng thứ hai chứa $n$ số nguyên ($1 \le c_i \le n$) — số thứ tự cột của bộ tách thứ $i$, với $i$ là số thứ tự hàng. Tất cả các số cột đều khác nhau.

Dòng thứ ba chứa một số nguyên duy nhất $m$ ($1 \le m \le 10^4$) — số lượng bóng.

Mỗi dòng trong số $m$ dòng tiếp theo chứa 3 số nguyên $x_i, y_i, t_i$ ($0 \le t_i \le 10^8$), mô tả thời điểm phóng các quả bóng — tại thời điểm $t_i$, một quả bóng sẽ xuất hiện tại ô $(x_i, y_i)$, ô này có chung cạnh với biên của lưới. Các thời điểm được đưa ra theo thứ tự không giảm của $t_i$. Tọa độ $(x_i, y_i)$ có thể nằm ở một trong bốn khu vực sau:

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

Đảm bảo rằng luôn tồn tại lời giải.

Dữ liệu ra

Dữ liệu ra nên chứa một dòng duy nhất gồm các ký tự 0 và 1. Ký tự thứ $i$ là 0 nếu bộ tách thứ $i$ không cần xoay, và 1 nếu ngược lại.

Ví dụ

Ví dụ 1

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

011

Ghi chú

Dưới đây là các vị trí mẫu của các quả bóng theo thời gian.