Вам дано дерево с \(n\) вершинами. Дерево подвешено за вершину \(1\), которая не считается листом не зависимо от ее степени.
Каждый лист покрашен в один из двух цветов: красный или синий. Листовая вершина с номером \(v\) исходно имеет цвет \(s_{v}\).
Цвет каждой из внутренней вершины (включая корень) определятся следующим образом.
- Обозначим за \(b\) количество синих непосредственных детей, и за \(r\) количество красных непосредственных детей данной вершины.
- Тогда цвет этой вершины синий тогда и только тогда, когда \(b - r \ge k\), иначе он красный.
Число \(k\) это параметр, одинаковый для всех вершин.
Вам необходимо обработать запросы следующих типов:
- 1 v: вывести цвет вершины \(v\);
- 2 v c: изменить цвет листа \(v\) на \(c\) (\(c = 0\) означает красный, \(c = 1\) означает синий);
- 3 h: изменить текущее значение \(k\) на \(h\).
Выходные данные
Для каждого запроса первого типа выведите \(0\), если цвет вершины \(v\) красный, и \(1\) иначе.
Примечание
(i) Исходное дерево
(ii) Дерево после 3-го запроса
(iii) Дерево после 7-го запроса
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
1 2
1 3
2 4
2 5
-1 -1 0 1 0
9
1 1
1 2
3 -2
1 1
1 2
3 1
2 5 1
1 1
1 2
|
0
0
1
1
0
1
|