Стайня

Обмеження: 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 (у стайні немає коня).