Farmer John 的农场里有 $N$ ($1\le N\le 2\cdot 10^5$) 头奶牛，编号为 $1\dots N$，每头奶牛都住在自己的牛棚里。每头奶牛 $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_i$ 决定举办另一种类型的派对。

每天晚上，每头奶牛都会尝试去参加一场派对。如果一头奶牛没有举办派对，她会查看她最好朋友的牛棚；如果那里也没有派对，她会跟随她最好的朋友去她们要去的地方（她的朋友也可能在跟随她自己的最好朋友，以此类推）。奶牛有可能永远找不到派对，在这种情况下，她当晚就会放弃。

请计算每个夜晚最终参加类型为 $C$、$O$ 和 $W$ 的派对的奶牛数量。

输入格式

第一行包含 $N$，即奶牛的数量。

第二行包含 $a_1,\dots, a_N$，其中 $a_i$ 是奶牛 $i$ 的最好朋友。

第三行包含 $M$，即夜晚的数量。

接下来的 $M$ 行，每行包含一个整数 $c_i$ ($1\le c_i\le N$) 和一个字符 $v_i$，分别代表举办派对的奶牛和派对的类型。

输出格式

输出 $M$ 行，其中第 $i$ 行包含 3 个以空格分隔的整数，分别表示在第 $i$ 个夜晚参加类型为 $C$、$O$ 和 $W$ 的派对的奶牛数量。

样例

样例输入 1

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

样例输出 1

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$，影响了奶牛 3、4 和 5。

在第 4 个夜晚，牛棚 2 的派对类型变更为 $O$，影响了奶牛 1 和 2。

子任务

• 测试点 2：$N, M\leq 100$
• 测试点 3-4：$N, M\leq 4000$
• 测试点 5-9：${a_i}$ 是 ${1,\dots, N}$ 的一个排列
• 测试点 10-21：无额外限制