Стайня

Обмеження: 7 сек., 512 МіБ

Як ви вже знаєте, у Зеника з Марічкою є \(n\) жеребців, пронумерованих від \(1\) до \(n\), яких вони тримають у стайні.

Наявність коней у стайні можна задати рядком \(t\) довжини \(n\), що складається із символів 0 і 1. \(t_i=\,\)1, якщо кінь з номером \(i\) зараз у стайні, та \(t_i=\,\)0, якщо він на пасовищі.

Задано рядок \(s\), що описує стайню зранку.

Протягом дня Марічка веде коней на пасовище та повертає до стайні.

За одну дію Марічка може:

• Відвести зі стайні на пасовище всіх жеребців з номерами від \(1\) до \(i\). Деякі з них можуть уже бути на пасовищі.

• Привести з пасовища до стайні всіх жеребців з номерами від \(1\) до \(i\). Деякі з них можуть уже бути в стайні.

Час від часу протягом дня Зеник питає в Марічки, чи є в стайні \(i\)-ий кінь?

Вам задано \(q\) запитів:

• 1 i 0 — Марічка відводить на пасовище коней з номерами від \(1\) до \(i\).

• 1 i 1 — Марічка приводить до стайні коней з номерами від \(1\) до \(i\).

• 2 i — Зеник питає в Марічки, чи \(i\)-ий кінь у стайні.

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

Вхідні дані

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

У другому рядку задано рядок \(s\).

У наступних \(q\) рядках задано запити в описаному вище форматі.

Вихідні дані

На кожне запитання Зеника виведіть відповідь в окремому рядку — 1, якщо в стайні є кінь, або 0, якщо нема.

Обмеження

\(1 \le n \le 5 \cdot 10^5\),

\(1 \le q \le 3 \cdot 10^5\),

рядок \(s\) складається із символів 0 і 1,

Зеник поставить принаймні одне питання Марічці.

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

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

• 19 балів: Марічка не приводить коней з пасовища до стайні,

• 12 балів: \(n \le 1000, q \le 1000\),

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

• 38 балів: без додаткових обмежень.

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 8 11011 1 4 1 2 3 1 5 0 2 3 2 5 1 4 1 2 3 2 5	1 0 0 1 0

Примітки

Розглянемо приклад.

• Марічка приводить коней з номерами від \(1\) до \(4\) з пасовища до стайні. Рядок стає 11111.

• Зеник запитує, чи є в стайні кінь з номером \(3\). Відповідь: 1 (у стайні є кінь).

• Марічка відводить коней з номерами від \(1\) до \(5\) на пасовище. Рядок стає 00000.

• Зеник запитує, чи є в стайні кінь з номером \(3\). Відповідь: 0 (у стайні немає коня).

• Зеник запитує, чи є в стайні кінь з номером \(5\). Відповідь: 0 (у стайні немає коня).

• Марічка приводить коней з номерами від \(1\) до \(4\) з пасовища до стайні. Рядок стає 11110.

• Зеник запитує, чи є в стайні кінь з номером \(3\). Відповідь: 1 (у стайні є конь).

• Зеник запитує, чи є в стайні кінь з номером \(5\). Відповідь: 0 (у стайні немає коня).