Рядок Зеника

Limits: 1 sec., 256 MiB

У Зеника є його улюблений бінарний рядок довжиною \(n\).

Бінарний рядок — це такий рядок, який складається лише із символів 0 і 1.

Марічка дуже любить упорядковані бінарні рядки, але Зеник не дозволяє їй сортувати свій рядок.

У Марічки появилося \(q\) запитань. Її цікавить, яким буде символ на позиції \(x\), якщо посортувати частину рядка між \(l\)-им і \(r\)-им символами включно.

Input

У першому рядку є два цілі числа \(n\) і \(q\) — довжина рядка й кількість запитань Марічки, відповідно.

У другому рядку є \(n\) символів 0 і 1.

У наступних \(q\) рядках записано по три цілі числа \(l\), \(r\) і \(x\) — ліву межу, праву межу підрядка й позицію, яка цікавить Марічку, відповідно.

Output

У відповідь на кожне питання Марічки виведіть 0 або 1 — символ, який буде на позиції, яка цікавить Марічку.

Constraints

\(2 \le n, q \le 10^5\),

\(s_i \in \{\texttt{0}, \texttt{1}\}\),

\(1 \le l \le x \le r \le n\).

Оцінювання задачі складається із наступних блоків:

1 бал — приклад з умови,

9 балів — \(n, q \le 200\), усі символи \(s\) однакові,

20 балів — \(n, q \le 200\),

30 балів — \(n, q \le 2 \cdot 10^4\),

40 балів — без додаткових обмежень.

Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 3 0101100 2 4 3 1 7 2 1 6 5	1 0 1

Notes

Запити не змінюють початкової стрічки. Якщо виконати перший запит, то стрічка буде виглядати так: 0011100, і на 3 позиції буде символ 1. Якщо виконати другий запит, то стрічка буде виглядати так: 0000111, і на 2 позиції буде символ 0. Якщо виконати третій запит, то стрічка буде виглядати так: 0001110, і на 5 позиції буде символ 1.