Вы никогда не задумывались над тем, сколько человек за год перевозят трамваи города с десятимиллионным населением, в котором каждый третий житель пользуется трамваем по два раза в день?

Предположим, что на планете Земля n городов, в которых есть трамваи. Любители статистики подсчитали для каждого из этих городов, сколько человек перевезено трамваями этого города за последний год. Из этих данных была составлена таблица, в которой города были отсортированы по алфавиту. Позже выяснилось, что для статистики названия городов несущественны, и тогда их просто заменили числами от 1 до n. Поисковая система, работающая с этими данными, должна уметь быстро отвечать на вопрос, есть ли среди городов с номерами от l до r такой, что за год трамваи этого города перевезли ровно x человек. Вам предстоит реализовать этот модуль системы.

В первой строке записано целое число n (1 ≤ n ≤ 69999). В следующей строке приведены статистические данные в виде списка целых чисел через пробел, i-е число в этом списке — количество человек, перевезенных за год трамваями i-го города. Все числа в списке положительны и не превосходят 10⁹ − 1. В третьей строке записано целое число q — количество запросов (1 ≤ q ≤ 69999). В следующих q строках перечислены запросы. Каждый запрос — это тройка целых чисел l, r и x, записанных через пробел (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 10⁹ − 1).

Выведите строку длины q, в которой i-й символ равен «1», если ответ на i-й запрос утвердителен, и «0» в противном случае.