31339번 - Puzzle 스페셜 저지다국어

문제

Once a puzzle has been gifted to Taja, and she still has no idea how to solve it.

The puzzle is a grid $n \times n,ドル with each row and each column containing exactly one separator, which is diagonal segment which starts in upper left corner and ends at lower right corner. Puzzle has a launch button, which launches the balls at integer time moments from the tubes, which are positioned at the boundary of the grid. Per one moment a ball moves to an adjacent cell. When a ball collides a separator it changes direction by 90ドル^\circ$. A ball disappears if it crosses border line.

To solve a puzzle, one needs to rotate some separators 90ドル^\circ$ around their centers, in such a way that no two balls will ever collide inside the grid.

Two balls collide if:

1. They are at the same cell at the same moment (if the cell contains separator, then both balls should be at the same side).

2. They collided at the cells' boundary (boundary of the whole grid counts as well).

In this problem you are to find any solution of this puzzle.

입력

First line of input contains single integer $n$ (1ドル \leq n \leq 500$) --- grid size.

Second line contains $n$ integers (1ドル \leq c_i \leq n$) --- column number of $i$th separator, which has $i$ as a row number. All column numbers are different.

Third line conatins single integer $m$ (1ドル \leq m \leq 10^4$) --- number of balls.

Each of the following $m$ lines contains 3ドル$ integers $x_i,ドル $y_i,ドル $t_i$ (0ドル \leq t_i \leq 10^8$), describing moments of balls' launches --- at the moment $t_i$ a ball will appear at $(x_i, y_i)$ cell, which shares common side with the boundary of the grid. Moments are given in non-decreasing order of $t_i$. Coordinates ($x_i, y_i$) can be at one of the four following areas:

1. $x_i = 0,ドル 1ドル \leq y_i \leq n$;
2. 1ドル \leq x_i \leq n,ドル $y_i = 0$;
3. $x_i = n + 1,ドル 1ドル \leq y_i \leq n$;
4. 1ドル \leq x_i \leq n,ドル $y_i = n + 1$.

It is guaranteed that solution always exists.

출력

Output should contain single line of 0ドル$ and 1ドル$. $i$th symbol is 0ドル,ドル if $i$th separator doesn't require rotation, 1ドル$ --- otherwise.

제한

힌트

Below are shown sample positions of the balls along the time.