CF1017G.The Tree

Abendsen assigned a mission to Juliana. In this mission, Juliana has a rooted tree with $n$ vertices. Vertex number $1$ is the root of this tree. Each vertex can be either black or white. At first, all vertices are white. Juliana is asked to process $q$ queries. Each query is one of three types:

1. If vertex $v$ is white, mark it as black; otherwise, perform this operation on all direct sons of $v$ instead.
2. Mark all vertices in the subtree of $v$ (including $v$) as white.
3. Find the color of the $i$-th vertex.

An example of operation "1 1" (corresponds to the first example test). The vertices $1$ and $2$ are already black, so the operation goes to their sons instead.

Can you help Juliana to process all these queries?

阿本德森给朱莉安娜布置了一项任务。在这项任务中，朱莉安娜拥有一棵包含 $n$ 个顶点的有根树，其中顶点编号为 $1$ 的节点是该树的根。每个顶点可以是黑色或白色；初始时，所有顶点均为白色。朱莉安娜需要处理 $q$ 个查询，每个查询属于以下三种类型之一：

1. 若顶点 $v$ 是白色，则将其染为黑色；否则，对 $v$ 的所有直接子节点执行此操作。
2. 将以 $v$ 为根的子树中（包括 $v$ 本身）的所有顶点染为白色。
3. 查询第 $i$ 个顶点的颜色。

操作 “1 1” 的示例（对应第一个样例测试）。顶点 $1$ 和 $2$ 已经是黑色，因此操作转而作用于它们的子节点。

你能帮助朱莉安娜处理所有这些查询吗？

The first line contains two integers $n$ and $q$ ($2\leq n\leq 10^5$, $1\leq q\leq 10^5$) — the number of vertices and the number of queries.

The second line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1\leq p_i \lt i$), where $p_i$ means that there is an edge between vertices $i$ and $p_i$.

Each of the next $q$ lines contains two integers $t_i$ and $v_i$ ($1\leq t_i\leq 3$, $1\leq v_i\leq n$) — the type of the $i$-th query and the vertex of the $i$-th query.

It is guaranteed that the given graph is a tree.

第一行包含两个整数 $n$ 和 $q$（$2\leq n\leq 10^5$，$1\leq q\leq 10^5$）—— 分别表示顶点数和查询次数。

第二行包含 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$（$1\leq p_i \lt i$），其中 $p_i$ 表示顶点 $i$ 与顶点 $p_i$ 之间存在一条边。

接下来的 $q$ 行中，每行包含两个整数 $t_i$ 和 $v_i$（$1\leq t_i\leq 3$，$1\leq v_i\leq n$）—— 分别表示第 $i$ 个查询的类型和第 $i$ 个查询所涉及的顶点。

保证所给图是一棵树。

For each query of type $3$, print "black" if the vertex is black; otherwise, print "white".

对于每个类型为 $3$ 的查询，如果该顶点为黑色，则输出 “black”；否则输出 “white”。

The first example is shown on the picture below.

The second example is shown on the picture below.

第一个示例如下图所示。

第二个示例如下图所示。