Как уже упоминалось, Василий любит играть в компьютерные игры. В одной из его любимых игр персонаж находится во вселенной, где каждая планета обозначается двоичным числом от \(0\) до \(2^n - 1\). На каждой из планет находятся врата, позволяющие перемещаться с планеты \(i\) на планету \(j\), если двоичная запись \(i\) отличается от двоичной записи \(j\) ровно в одном бите.
Василий хочет проверить вас и посмотреть, как вы справитесь с обработкой следующих запросов в этом игровом мире:
- Уничтожить планеты с номерами от \(l\) до \(r\) включительно. На такие планеты больше нельзя перемещаться.
- Узнать, можно ли с планеты \(a\) долететь до планеты \(b\), используя какое-то количество планетных врат. Гарантируется, что планеты \(a\) и \(b\) не являются уничтоженными.
Выходные данные
На каждый запрос типа ask в отдельной строке необходимо вывести «1», если с планеты \(a\) можно долететь до планеты \(b\), и «0» иначе (без кавычек).
Примечание
Первый тест можно визуализировать следующим образом:
Ответ на запрос ask 0 7 положительный.
Далее после запроса block 3 6 граф будет выглядеть следующим образом (выделены уничтоженные вершины):
Ответ на запрос ask 0 7 отрицательный, так как любой путь из вершины \(0\) в вершину \(7\) лежит через одну из уничтоженных вершин.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
ask 0 7
block 3 6
ask 0 7
|
1
0
|
|
2
|
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
|