Tajaはパズルをプレゼントされましたが、解き方が全く分かりません。

このパズルは $n \times n$ のグリッドで構成されており、各行と各列にちょうど1つずつセパレーターが含まれています。セパレーターは、左上の角から始まり右下の角で終わる対角線状のセグメントです。パズルには発射ボタンがあり、グリッドの境界に配置されたチューブから整数時刻にボールを発射します。ボールは1時刻につき隣接するセルへ移動します。ボールがセパレーターに衝突すると、その進行方向は $90^\circ$ 変化します。ボールが境界線を越えると消滅します。

パズルを解くには、いくつかのセパレーターをその中心を軸に $90^\circ$ 回転させ、グリッド内で2つのボールが決して衝突しないようにする必要があります。

2つのボールが衝突する条件は以下の通りです。

1. 同じ時刻に同じセルに存在する場合（セルにセパレーターが含まれている場合は、両方のボールがセパレーターの同じ側にある必要があります）。
2. セルの境界で衝突した場合（グリッド全体の境界も含まれます）。

この問題では、このパズルの任意の解を求めてください。

入力

入力の最初の行には、グリッドのサイズを表す整数 $n$ ($1 \le n \le 500$) が含まれます。 2行目には、$n$ 個の整数 ($1 \le c_i \le n$) が含まれます。これは、$i$ 行目にあるセパレーターの列番号を表します。すべての列番号は異なります。 3行目には、ボールの数を表す整数 $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)$ は以下の4つの領域のいずれかにあります。

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からなる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

注記

以下に、時間経過に伴うボールのサンプル位置を示します。

Figure 1. パズルのグリッドとセパレーターの構成図