Page not loading? Try clicking here.
Placeholder

#8858
Subtask

COW Traversals 1s 1024MB

Problems

There are N (1≤N≤2⋅10^5) cows labeled 1…N on Farmer John's farm, where each cow lives in its own barn. Each cow i has a best friend a_i (1≤a_i≤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≤M≤2⋅10^5) consecutive nights.

On night i, cow c_i will decide to throw a party of type ti at its barn, where t_i∈"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

The first line contains N, the number of cows.

The second line contains a_1,…,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≤c_i≤N) and a character v_i, representing the cow that is throwing the party and the party type respectively.


Output

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


Subtask

# Score Condition
#110

N,M\le 100

#220

N,M\le 4\ 000

#330

\{a_i\} is a permutation of \{1,…,N\}

#440

No additional constraints


Example 

5
2 3 4 5 4
4
2 C
4 C
4 W
2 O
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.


Source

USACO 2026 First Contest, Gold

You must sign in to write code.