Taja 收到了一份拼图，但她完全不知道该如何解决它。

该拼图是一个 $n \times n$ 的网格，每一行和每一列都恰好包含一个分隔符。分隔符是一个从左上角指向右下角的对角线段。拼图有一个启动按钮，可以在整数时刻从位于网格边界的管道中发射小球。在每一个时刻，小球会移动到相邻的单元格。当小球撞到分隔符时，它会改变 $90^\circ$ 的方向。如果小球穿过边界线，它就会消失。

为了解决这个拼图，需要将一些分隔符绕其中心旋转 $90^\circ$，使得没有任何两个小球在网格内部发生碰撞。

两个小球发生碰撞的情况如下： 1. 它们在同一时刻处于同一个单元格（如果该单元格包含分隔符，则两个小球必须处于分隔符的同一侧）。 2. 它们在单元格的边界上发生碰撞（整个网格的边界也计算在内）。

在本题中，你需要找到该拼图的任意一种解法。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500$)，表示网格大小。 第二行包含 $n$ 个整数 ($1 \le c_i \le n$)，表示第 $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

说明

下方展示了小球随时间变化的示例位置。