Задачі
Для любителів статистики
Для любителів статистики
Ви ніколи не задумувались над тим, скільки чоловік за рік перевозять трамваї маста з десятимільонним населенням, у якому кожен третій житель користується трамваєм по два раза на день?
Припустимо, що на планеті Земля \textbf{n} міст, у яких є трамваї. Любителі статистики підрахували для кожного з цих міст, скільки чоловік перевезено трамваями цього міста за останній рік. За цими даними була складена таблиця, у якій міста були відсортовані по алфавіту. Пізніше вияснилось, що для статистики назви міст несуттєві, і тоді їх просто замінили числами від \textbf{1} до \textbf{n}. Пошукова система, яка працює з цими даними, повинна вміти швидко відповідати на питання, чи є серед міст з номерами від \textbf{l} до \textbf{r} таке, що за рік трамваї цього міста перевезли рівно \textbf{x} чоловік. Вам належить реалізувати цей модуль системи.
\InputFile
У першому рядку задано ціле число \textbf{n}, \textbf{0} < \textbf{n} < \textbf{70000}. У наступному рядку приведено статистичні дані у вигляді списку цілих чисел через пропуск, \textbf{i}-е число у цьому списку --- кількість человік, перевезених за рік трамваями \textbf{i}-го міста. Усі числа у списку додатні і не перевищують \textbf{10^9−1}. У третьому рядку задано кількість запитів \textbf{q}, \textbf{0} < \textbf{q} < \textbf{70000}. У наступних \textbf{q} рядках перераховано запити. Кожен запит --- це трійка цілих чисел \textbf{l}, \textbf{r} та \textbf{x}, записаних через пропуск; \textbf{1} ≤ \textbf{l} ≤ \textbf{r} ≤ \textbf{n}; \textbf{0} < \textbf{x} < \textbf{10^9}.
\OutputFile
Виведіть рядок довжини \textbf{q}, у якому \textbf{i}-й символ дорівнює "\textbf{1}", якщо відповідь на \textbf{i}-й запит ствердна, і "\textbf{0}" у протилежному випадку.
Вхідні дані #1
5 123 666 314 666 434 5 1 5 314 1 5 578 2 4 666 4 4 713 1 1 123
Вихідні дані #1
10101