Pattern Coloring

Given an integer sequence (a_1, a_2, ..., a_N) and (M) patterns of the form ((x, y, d)), we define a segment of the sequence (a_l, ..., a_r) as covered by the pattern ((x, y, d)) if the following conditions are met:

• (r - l + 1 = d);

• (a_l = x);

• (a_r = y).

Your task is to identify all elements in the sequence that are covered by at least one pattern.

Input

The first line of the input contains an integer (N) ((1 $\le$ N $\le$ 5 $\times$ 10^4)) representing the length of the sequence. The second line contains the integers (a_1, a_2, ..., a_N) ((-10^8 $\le$ a_i $\le$ 10^8)), separated by spaces. The third line contains an integer (M) ((1 $\le$ M $\le$ 5 $\times$ 10^4)), which is the number of patterns. Each of the following (M) lines contains three integers (x_i, y_i, d_i) ((-10^8 $\le$ x_i, y_i $\le$ 10^8; 2 $\le$ d_i $\le$ 20)), defining the (i)-th pattern.

Output

Output a string of length (N) consisting of zeros and ones. The (i)-th position should contain a one if the element (a_i) is covered by at least one pattern, and a zero otherwise.

Examples