Problem 1. COW Traversals

USACO 2026 First Contest, Gold

There are $N$ ($1\le N\le 2\cdot 10^5$) cows labeled $1\dots N$ on Farmer John's farm, where each cow lives in its own barn. Each cow $i$ has a best friend $a_i$ ($1\le a_i\le N$). Cows can be best friends with themselves, and multiple cows can have the same best friend. The cows love to party, so they have decided to throw a party for $M$ ($1\le M\le 2\cdot 10^5$) consecutive nights.

On night $i$, cow $c_i$ will decide to throw a party of type $t_i$ at its barn, where $t_i\in \texttt{"COW"}$. This party will exist for all future nights as well, until cow $c_i$ decides to throw a party of a different type.

Every night, each cow will attempt to go to a party. If a cow is not hosting a party, they will check their best friend's barn, and if there is no party there, will follow their best friend to wherever they are going (who might also follow their best friend and so on). It is possible that a cow might never find a party and will then give up for the night.

Compute for each night, the number of cows that end up at a party of type $C$, $O$, and $W$ respectively.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$, the number of cows.

The second line contains $a_1,\dots, a_N$, where $a_i$ is cow $i$'s best friend.

The third line contains $M$, the number of nights.

The next $M$ lines each contain an integer $c_i$ ($1\le c_i\le N$) and a character $v_i$, representing the cow that is throwing the party and the party type respectively.

OUTPUT FORMAT (print output to the terminal / stdout):

Output $M$ lines, where the $i$th consists of $3$ space-separated integers, the number of cows going to parties of type $C$, $O$, and $W$ on the $i$th night, respectively.

SAMPLE INPUT:

5
2 3 4 5 4
4
2 C
4 C
4 W
2 O

SAMPLE OUTPUT:

2 0 0
5 0 0
2 0 3
0 2 3

On night $1$, there is only one party of type $C$ at barn $2$, which only cows $1$ and $2$ attend.

On night $2$, there is a new party of type $C$ at barn $4$, which cows $3$, $4$, and $5$ can now reach.

On night $3$, the party at barn $4$ is changed to type $W$, affecting cows $3$, $4$ and $5$.

On night $4$, the party at barn $2$ is changed to type $O$, affecting cows $1$ and $2$.

SCORING: Input 2: $N, M\leq 100$Inputs 3-4: $N, M\leq 4000$Inputs 5-9: $\{a_i\}$ is a permutation of $\{1,\dots, N\}$Inputs 10-21: No additional constraints

Problem credits: Benjamin Qi