Broccoli or Cauliflower

Time Limit : 2 sec, Memory Limit : 262144 KB
Japanese version is here

E: Broccoli or Cauliflower

Problem

The input is a rooted tree T = (V, E) with n vertices. Note that n is odd and the vertex with index 1 is the root of T. In addition, we give a label G or W for each vertex. Let T_v = (U, F) be a subtree of T such that U is defined as following.

  • U = $\{$ u \in V \ \ | \ \ u $\text{ is the descendant of }$ v $\}$

We call T_v a subtree of v.

We consider the following operation and perform operations q times.

  • Let v be a vertex. If a vertex u \in U has the label G, then we change the label of u G to W. Otherwise, we change the label of u W to G.

After each operation, output gbroccolih if the number of vertices with the label G is greater than W. Otherwise, output gcauliflowerh.

Input format

An input is the following format.

n q
p_2 ... p_n
c_1 ... c_n
v_1
$\vdots$
v_q

In line 1, there are two integers n and q, where n is the number of vertices in T and q is the number of queries. Note that n is odd.

In line 2, there are n - 1 integers p_2 to p_n. p_i represents the parent of a vertex v_i.

In line 3, there are n characters c_1 to c_n. c_i represents the label of v_i. Finally, in line j + 3, there is an integer v_j. We perform the operation for T_{v_j}.

Constraints

  • 1 \leq n \leq 100,000 ( n is odd. )
  • 1 \leq q \leq 100,000
  • 1 \leq p_i < ii2 \leq i \leq nj
  • c_j is G or W. (1 \leq j \leq n)
  • 1 \leq v_i \leq ni1 \leq i \leq qj

Output format

An output consists q lines and output gbroccolih or gcauliflowerh in each line.

Input example 1

7 4
1 1 2 2 3 3
G G W W W G G 
2
1
3
4

Output example 1

broccoli
cauliflower
cauliflower
broccoli

Input example 2

17 18
1 1 1 3 1 4 2 4 3 6 10 9 3 4 5 15
W W W W W W W W G W G G W G W W W
6
7
1
9
14
6
4
5
3
7
8
13
9
6
14
12
9
13

Output example 2

cauliflower
cauliflower
broccoli
broccoli
broccoli
broccoli
broccoli
broccoli
broccoli
cauliflower
cauliflower
cauliflower
cauliflower
cauliflower
broccoli
cauliflower
cauliflower
cauliflower