타자(Taja)에게 퍼즐 하나가 선물로 주어졌지만, 그녀는 여전히 그것을 어떻게 풀어야 할지 전혀 모르는 상태입니다.

이 퍼즐은 $n \times n$ 격자로 구성되어 있으며, 각 행과 각 열에는 정확히 하나의 구분선(separator)이 포함되어 있습니다. 구분선은 왼쪽 위 모서리에서 시작하여 오른쪽 아래 모서리로 이어지는 대각선 형태의 선분입니다. 퍼즐에는 발사 버튼이 있는데, 이 버튼을 누르면 격자의 경계에 위치한 튜브에서 정수 시간 단위로 공이 발사됩니다. 공은 한 번의 시간 단위마다 인접한 칸으로 이동합니다. 공이 구분선과 충돌하면 진행 방향이 $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$번째 문자가 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. 퍼즐의 격자와 구분선 예시