H - Feliz árbol pequeño

Time limit: 3 seconds
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

Kappa tiene un feliz árbol pequeño con raíz y $n$ nodos. El amigo de Kappa, Keepo, tiene un nodo favorito en este árbol. A Kappa no le importa dejar jugar a Keepo con su árbol, pero este tiene que seguir sus reglas: él permite a Keepo recorrer el árbol solamente en preorden (DFS - depth-first search). Además, los nodos están numerados de $0$ a $n - 1$, y cada nodo tiene un color blanco o negro. Esto también limita la forma de recorrer el árbol. A continuación se muestra el pseudocódigo usado:

$\verb|DFS(tree T):|$
$\verb|    visit T’s root u|$
$\verb|    if(u is white):|$
$\verb|        for(all u’s child v, in ascending order by their index):|$
$\verb|            DFS(subtree rooted at v)|$
$\verb|    else:|$
$\verb|        for(all u’s child v, in descending order by their index):|$
$\verb|            DFS(subtree rooted at v)|$

La raíz está numerada con $0$, y cada nodo diferente a la raíz tiene un número mayor que su padre. A Keepo le gusta más el nodo $n - 1$, pero él no quisiera pasar mucho tiempo recorriendo el árbol. Por lo tanto, Keepo te pide que lo ayudes a determinar la cantidad de nodos que debe visitar antes de alcanzar su nodo favorito. Lo que hace las cosas más complicadas es que Kappa y Keepo cambian de idea frecuentemente. Algunas veces Kappa decide cambiar el color de todos los nodos en un subárbol, algunas veces Keepo cambia su nodo favorito. Luego de cada cambio, tú debes decirle a Keepo la nueva respuesta.

Input

La primera línea de la entrada contiene un entero $n$ $(1 \leq n \leq 10^5)$, el número de nodos. Al inicio, todos los nodos son blancos. La segunda línea contiene $n - 1$ enteros $p_1, p_2, ..., p_{n-1}$. $p_i$ $(0 \leq p_i \lt i)$ es el número que identifica al padre del nodo $i$. La tercera línea contiene $q$ $(1 \leq q \leq 10^5)$ enteros, el número de cambios. Las siguientes $q$ líneas representan un cambio cada una. En cada línea, hay un caracter y un número $u$ $(1 \leq u \lt n)$. Si el caracter es $\texttt{`a'}$, significa que Kappa cambia el color de todos los nodos en el subárbol con raíz en $u$. Si el caracter es $\texttt{`e'}$, significa que Keepo cambia su nodo favorito a $u$.

Output

La primera línea contiene el número de nodos que se deben visitar antes del nodo $n - 1$. Las siguientes $q$ líneas contienen la nueva respuesta despues de cada cambio.

Sample test(s)

Input
4 0 0 1 2 a 0 e 2
Output
2 3 1