Абендсен дал задание Джулиане. Она имеет корневое дерево из \(n\) вершин. Вершина номер \(1\) является корнем дерева. Каждая вершина может быть либо чёрной, либо белой. Сначала все вершины белые. Джулиана должна обработать \(q\) запросов одного из трёх типов:
- Если вершина \(v\) белая, перекрасить её в чёрный цвет; в другом случае вместо этого выполнить эту операцию со всеми непосредственными сыновьями \(v\).
- Перекрасить все вершины поддерева \(v\) (включая \(v\)) в белый цвет.
- Найти цвет \(i\)-й вершины.
Пример операции "1 1" (соответствует операции из первого примера). Вершины \(1\) и \(2\) уже черные, поэтому операция переходит к их сыновьям. Можете помочь Джулиане обработать все запросы?
Выходные данные
Для каждого запроса типа \(3\) выведите «black», если вершина чёрная; в другом случае выведите «white».
Примечание
Первый пример показан на рисунке ниже.
Второй пример показан на рисунке ниже.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 10
1 2 1 2 5 4 5
1 2
3 2
3 1
1 1
1 1
3 5
3 7
3 4
2 2
3 5
|
black
white
black
white
black
white
|
|
2
|
8 11
1 1 2 3 3 6 6
1 1
1 1
1 3
3 2
3 4
3 6
3 7
2 3
1 6
3 7
3 6
|
black
white
black
white
white
black
|