G. Врата в другой мир
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Как уже упоминалось, Василий любит играть в компьютерные игры. В одной из его любимых игр персонаж находится во вселенной, где каждая планета обозначается двоичным числом от $$$0$$$ до $$$2^n - 1$$$. На каждой из планет находятся врата, позволяющие перемещаться с планеты $$$i$$$ на планету $$$j$$$, если двоичная запись $$$i$$$ отличается от двоичной записи $$$j$$$ ровно в одном бите.

Василий хочет проверить вас и посмотреть, как вы справитесь с обработкой следующих запросов в этом игровом мире:

  • Уничтожить планеты с номерами от $$$l$$$ до $$$r$$$ включительно. На такие планеты больше нельзя перемещаться.
  • Узнать, можно ли с планеты $$$a$$$ долететь до планеты $$$b$$$, используя какое-то количество планетных врат. Гарантируется, что планеты $$$a$$$ и $$$b$$$ не являются уничтоженными.
Входные данные

Первая строка содержит два целых числа $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 50$$$, $$$1 \leq m \leq 5 \cdot 10^4$$$) — количество бит в двоичной записи каждой планеты и количество запросов соответственно.

Следующие $$$m$$$ строк ввода содержат запросы двух видов:

block l r — запрос на уничтожение планет, с номерами от $$$l$$$ до $$$r$$$ включительно ($$$0 \le l \le r < 2^n$$$). Гарантируется, что никакая планета не будет уничтожена дважды.

ask a b — запрос на достижимость между планетами $$$a$$$ и $$$b$$$ ($$$0 \le a, b < 2^n$$$). Гарантируется, что планеты $$$a$$$ и $$$b$$$ еще не были уничтожены.

Выходные данные

На каждый запрос типа ask в отдельной строке необходимо вывести «1», если с планеты $$$a$$$ можно долететь до планеты $$$b$$$, и «0» иначе (без кавычек).

Примеры
Входные данные
3 3
ask 0 7
block 3 6
ask 0 7
Выходные данные
1
0
Входные данные
6 10
block 12 26
ask 44 63
block 32 46
ask 1 54
block 27 30
ask 10 31
ask 11 31
ask 49 31
block 31 31
ask 2 51
Выходные данные
1
1
0
0
1
0
Примечание

Первый тест можно визуализировать следующим образом:

Ответ на запрос ask 0 7 положительный.

Далее после запроса block 3 6 граф будет выглядеть следующим образом (выделены уничтоженные вершины):

Ответ на запрос ask 0 7 отрицательный, так как любой путь из вершины $$$0$$$ в вершину $$$7$$$ лежит через одну из уничтоженных вершин.