Безумный ученый Майк построил корневое дерево, которое состоит из n вершин. Каждая вершина представляет собой резервуар, который может быть либо пуст, либо заполнен водой.
Вершины дерева пронумерованы числами от 1 до n. Корень дерева находится в вершине 1. Резервуары детей каждой вершины расположены ниже резервуара этой вершины, при этом вершина соединена с каждым из детей трубой, по которой вниз может стекать вода.
Майк хочет выполнять с деревом следующие операции:
- Заполнить водой вершину v. Тогда v и все ее потомки (дети, дети детей, и так далее) заполняются водой.
- Опустошить вершину v. Тогда v и все ее предки становятся пустыми.
- Определить, заполнена ли вершина v водой в данный момент.
Изначально все вершины дерева пусты.
Майк уже составил полный список операций, которые он хочет выполнить по порядку. Перед испытанием дерева Майк решил провести симуляцию этих действий. Помогите Майку определить, какие результаты он получит в результате выполнения всех операций.
Выходные данные
Для каждой операции типа 3 выведите на отдельной строке 1, если вершина заполнена, и 0, если вершина пуста. Ответы на запросы выводите в том порядке, в котором запросы даны во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
5 1
2 3
4 2
12
1 1
2 3
3 1
3 2
3 3
3 4
1 2
2 4
3 1
3 3
3 4
3 5
|
0
0
0
1
0
1
0
1
|