题目描述

Farmer John 的农场上有 \(N\) 头奶牛，编号为 \(1 \dots N\)，满足 \(1 \le N \le 2 \cdot 10^5\)。每头奶牛都住在自己的牛棚里。

第 \(i\) 头奶牛有一个最好的朋友 \(a_i\)，满足 \(1 \le a_i \le N\)。一头奶牛可以把自己当作自己的最好朋友，也可能有多头奶牛拥有同一个最好朋友。

奶牛们很喜欢开派对，因此她们决定连续 \(M\) 个晚上都举办派对，满足 \(1 \le M \le 2 \cdot 10^5\)。

在第 \(i\) 个晚上，奶牛 \(c_i\) 会在自己的牛棚举办一个类型为 \(t_i\) 的派对，其中 \(t_i \in \texttt{"COW"}\)。

一场派对一旦被举办，就会在之后的每个晚上都持续存在，直到这头奶牛又举办了另一种类型的新派对为止。

每个晚上，每头奶牛都会尝试去参加某场派对：

• 如果它自己正在举办派对，那么它就去自己的派对
• 否则，它会先查看自己最好朋友的牛棚
• 如果那里也没有派对，它就会跟着最好朋友前往最好朋友准备去的地方
• 这个过程会不断递归下去

有些奶牛最终可能永远找不到任何派对，这种情况下它们当晚就不参加任何派对。

请你对每个晚上分别求出：最终参加 \(C\)、\(O\)、\(W\) 三种类型派对的奶牛数量。

输入格式

第一行包含整数 \(N\)。

第二行包含 \(N\) 个整数 \(a_1,\dots,a_N\)，表示每头奶牛的最好朋友。

第三行包含整数 \(M\)。

接下来 \(M\) 行，每行包含一个整数 \(c_i\) 和一个字符 \(v_i\)，表示第 \(i\) 个晚上由奶牛 \(c_i\) 举办类型为 \(v_i\) 的派对。

输出格式

输出 \(M\) 行。第 \(i\) 行输出三个整数，分别表示第 \(i\) 个晚上参加 \(C\)、\(O\)、\(W\) 三种派对的奶牛数量。

样例

输入

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

说明

第 1 个晚上，只有奶牛 \(2\) 在举办类型为 \(C\) 的派对，因此只有奶牛 \(1\) 和 \(2\) 能到达某场派对。

第 2 个晚上，奶牛 \(4\) 新开了一场类型为 \(C\) 的派对，于是奶牛 \(3,4,5\) 也都能参加派对。

第 3 个晚上，奶牛 \(4\) 的派对类型改成了 \(W\)，因此受影响的是能到达它的那些奶牛。

第 4 个晚上，奶牛 \(2\) 的派对类型改成了 \(O\)。

数据范围

• 输入 2：\(N,M \le 100\)
• 输入 3-4：\(N,M \le 4000\)
• 输入 5-9：数组 \(\{a_i\}\) 是一个排列
• 输入 10-21：无额外限制

命题信息

原题命题：Benjamin Qi