Pattern Coloring#2002
Given an integer sequence a_1, a_2, \ldots, a_N and patterns of the form (x, y, d), we say that a segment a_l, \ldots, a_r is covered by the pattern (x, y, d) if the following conditions are satisfied:
r - l + 1 = d;
a_l = x;
a_r = y.
Find all elements in the sequence that are covered by at least one pattern.
The first line contains an integer (1 \leq N \leq 5 \times 10^4) — the length of the sequence.
The second line contains integers a_1, a_2, \ldots, a_N (-10^8 \leq a_i \leq 10^8), separated by spaces.
The third line contains an integer (1 \leq M \leq 5 \times 10^4) — the number of patterns.
Each of the next lines contains three integers x_i, y_i, d_i (-10^8 \leq x_i, y_i \leq 10^8;\ 2 \leq d_i \leq 20), defining the -th pattern.
Output a string of length consisting of zeros and ones. The -th position must be one if the element a_i is covered by at least one pattern, and zero otherwise.
Example 1