Дистанционный практикум по программированию

Дана целочисленная последовательность a₁, a₂, ..., a_N и M паттернов вида (x, y, d). Будем говорить, что часть последовательности a_l, ..., a_r покрывается паттерном (x, y, d), если:

·      r – l + 1 = d;

·      a_l = x;

·      a_r = y.

Найдите все элементы последовательности, которые покрыты хотя бы одним паттерном.

В первой строке входного файла записано целое число N (1 ≤ N ≤ 5∙10⁴) — длина последовательности. Во второй строке через пробел записаны целые числа a₁, a₂, ..., a_N (−10⁸ ≤ a_i ≤ 10⁸). В третьей строке записано целое число M (1 ≤ M ≤ 5∙10⁴) — количество паттернов. В i-й из следующих M строк записаны три целых числа x_i, y_i, d_i, которые задают i-й паттерн (−10⁸ ≤ x_i, y_i ≤ 10⁸; 2 ≤ d_i ≤ 20).

В выходной файл выведите строку длины N, состоящую из нулей и единиц. На i-й позиции должна стоять единица, если элемент a_i покрыт хотя бы одним паттерном и ноль в противном случае.

Пример

Поток ввода	Поток вывода
5 1 2 3 4 5 3 2 3 2 3 4 2 1 5 4	01110