Покраска паттернов
Дана целочисленная последовательность a_1, a_2, ..., 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^4) — длина последовательности. Во второй строке через пробел записаны целые числа a_1, a_2, ..., a_N (−10^8 ≤ a_i ≤ 10^8). В третьей строке записано целое число M (1 ≤ M ≤ 5∙10^4) — количество паттернов. В i-й из следующих M строк записаны три целых числа x_i, y_i, d_i, которые задают i-й паттерн (−10^8 ≤ x_i, y_i ≤ 10^8; 2 ≤ d_i ≤ 20).
Выходные данные
В выходной файл выведите строку длины N, состоящую из нулей и единиц. На i-й позиции должна стоять единица, если элемент a_i покрыт хотя бы одним паттерном и ноль в противном случае.