{"raw_statement":[{"iden":"statement","content":"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:\n\n1. If vertex $v$ is white, mark it as black; otherwise, perform this operation on all direct sons of $v$ instead.\n2. Mark all vertices in the subtree of $v$ (including $v$) as white.\n3. Find the color of the $i$\\-th vertex.\n\n 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?"},{"iden":"input","content":"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.\n\nThe second line contains $n-1$ integers $p_2, p_3, \\ldots, p_n$ ($1\\leq p_i<i$), where $p_i$ means that there is an edge between vertices $i$ and $p_i$.\n\nEach 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.\n\nIt is guaranteed that the given graph is a tree."},{"iden":"output","content":"For each query of type $3$, print \"_black_\" if the vertex is black; otherwise, print \"_white_\"."},{"iden":"examples","content":"Input\n\n8 10\n1 2 1 2 5 4 5\n1 2\n3 2\n3 1\n1 1\n1 1\n3 5\n3 7\n3 4\n2 2\n3 5\n\nOutput\n\nblack\nwhite\nblack\nwhite\nblack\nwhite\n\nInput\n\n8 11\n1 1 2 3 3 6 6\n1 1\n1 1\n1 3\n3 2\n3 4\n3 6\n3 7\n2 3\n1 6\n3 7\n3 6\n\nOutput\n\nblack\nwhite\nblack\nwhite\nwhite\nblack"},{"iden":"note","content":"The first example is shown on the picture below.\n\nThe second example is shown on the picture below.\n\n"}],"translated_statement":[{"iden":"statement","content":"Abendsen 为 Juliana 安排了一项任务。在这项任务中，Juliana 拥有一棵包含 $n$ 个顶点的有根树，顶点编号为 $1$ 的是树的根。每个顶点可以是黑色或白色。最初，所有顶点都是白色的。Juliana 需要处理 $q$ 个查询，每个查询属于以下三种类型之一：\n\n你能帮助 Juliana 处理所有这些查询吗？\n\n第一行包含两个整数 $n$ 和 $q$（$2 lt.eq n lt.eq 10^5$，$1 lt.eq q lt.eq 10^5$）——顶点数和查询数。\n\n第二行包含 $n -1$ 个整数 $p_2, p_3, dots.h, p_n$（$1 lt.eq p_i < i$），其中 $p_i$ 表示顶点 $i$ 和 $p_i$ 之间有一条边。\n\n接下来的 $q$ 行中，每行包含两个整数 $t_i$ 和 $v_i$（$1 lt.eq t_i lt.eq 3$，$1 lt.eq v_i lt.eq n$）——第 $i$ 个查询的类型和第 $i$ 个查询的顶点。\n\n保证给定的图是一棵树。\n\n对于每个类型为 $3$ 的查询，如果该顶点是黑色，则输出 \"_black_\"；否则输出 \"_white_\"。\n\n第一个示例如下图所示。\n\n第二个示例如下图所示。\n\n"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $q$（$2 lt.eq n lt.eq 10^5$，$1 lt.eq q lt.eq 10^5$）——顶点数和查询数。第二行包含 $n -1$ 个整数 $p_2, p_3, dots.h, p_n$（$1 lt.eq p_i < i$），其中 $p_i$ 表示顶点 $i$ 和 $p_i$ 之间有一条边。接下来的 $q$ 行中，每行包含两个整数 $t_i$ 和 $v_i$（$1 lt.eq t_i lt.eq 3$，$1 lt.eq v_i lt.eq n$）——第 $i$ 个查询的类型和第 $i$ 个查询的顶点。保证给定的图是一棵树。"},{"iden":"output","content":"对于每个类型为 $3$ 的查询，如果该顶点是黑色，则输出 \"_black_\"；否则输出 \"_white_\"。"},{"iden":"examples","content":"输入\n8 10\n1 2 1 2 5 4 5\n1 2\n3 2\n3 1\n1 1\n1 1\n3 5\n3 7\n3 4\n2 2\n3 5\n输出\nblack\nwhite\nblack\nwhite\nblack\nwhite\n\n输入\n8 11\n1 1 2 3 3 6 6\n1 1\n1 1\n1 3\n3 2\n3 4\n3 6\n3 7\n2 3\n1 6\n3 7\n3 6\n输出\nblack\nwhite\nblack\nwhite\nwhite\nblack"},{"iden":"note","content":"第一个示例如下图所示。第二个示例如下图所示。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions** \nLet $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \\{1, 2, \\dots, n\\} $ and vertex $ 1 $ is the root. \nLet $ \\text{parent}(v) = p_v $ for $ v \\in \\{2, \\dots, n\\} $, where $ p_v \\in V $ and $ p_v < v $. \nLet $ c: V \\to \\{\\text{white}, \\text{black}\\} $ be the color function, initialized as $ c(v) = \\text{white} $ for all $ v \\in V $. \n\n**Constraints** \n1. $ 2 \\le n \\le 10^5 $ \n2. $ 1 \\le q \\le 10^5 $ \n3. For each $ v \\in \\{2, \\dots, n\\} $, $ 1 \\le p_v < v $ \n4. For each query $ i \\in \\{1, \\dots, q\\} $: \n - $ t_i \\in \\{1, 2, 3\\} $ \n - $ v_i \\in \\{1, \\dots, n\\} $ \n\n**Operations** \nFor each query $ (t_i, v_i) $: \n- If $ t_i = 1 $: Set $ c(u) = \\text{black} $ for all $ u \\in \\text{subtree}(v_i) $. \n- If $ t_i = 2 $: Set $ c(u) = \\text{white} $ for all $ u \\in \\text{subtree}(v_i) $. \n- If $ t_i = 3 $: Output $ c(v_i) $. \n\n**Objective** \nFor each query of type $ 3 $, output the current color of vertex $ v_i $.","simple_statement":null,"has_page_source":false}