Taja 收到了一個拼圖，但她完全不知道該如何解開它。

這個拼圖是一個 $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$ 個分隔器不需要旋轉，則第 $i$ 個符號為 0，否則為 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

說明

下方展示了球隨時間變化的範例位置。