Для любителів статистики
Ви ніколи не задумувались над тим, скільки чоловік за рік перевозять трамваї маста з десятимільонним населенням, у якому кожен третій житель користується трамваєм по два раза на день?
Припустимо, що на планеті Земля n міст, у яких є трамваї. Любителі статистики підрахували для кожного з цих міст, скільки чоловік перевезено трамваями цього міста за останній рік. За цими даними була складена таблиця, у якій міста були відсортовані по алфавіту. Пізніше вияснилось, що для статистики назви міст несуттєві, і тоді їх просто замінили числами від 1 до n. Пошукова система, яка працює з цими даними, повинна вміти швидко відповідати на питання, чи є серед міст з номерами від l до r таке, що за рік трамваї цього міста перевезли рівно x чоловік. Вам належить реалізувати цей модуль системи.
Вхідні дані
У першому рядку задано ціле число n, 0 < n < 70000. У наступному рядку приведено статистичні дані у вигляді списку цілих чисел через пропуск, i-е число у цьому списку — кількість человік, перевезених за рік трамваями i-го міста. Усі числа у списку додатні і не перевищують 10^9−1. У третьому рядку задано кількість запитів q, 0 < q < 70000. У наступних q рядках перераховано запити. Кожен запит — це трійка цілих чисел l, r та x, записаних через пропуск; 1 ≤ l ≤ r ≤ n; 0 < x < 10^9.
Вихідні дані
Виведіть рядок довжини q, у якому i-й символ дорівнює "1", якщо відповідь на i-й запит ствердна, і "0" у протилежному випадку.