该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

点击此处下载附加样例文件

题目描述

有 N 个画家，要在接下来的 M 天举办若干场画展。

画展分成油画展、水彩画展、素描画展三类，分别用 A、B、C 表示。

我们把画家从 1 ~ N 进行编号。比较奇怪的是，每个画家最多只认识其中的一个画家。记画家 i 认识的画家是 Ti。需要注意的是，认识不是相互的，即 x 认识 y，y 不一定认识 x。可能有同一个画家被很多人认识。还可能有的画家谁也不认识，此时 Ti=i，表示他只认识自己。

在第 i 天，画家 Pi 会举办类型为 Ki (Ki ∈ { A, B, C }) 的画展，并且在接下来的每天，他都会持续举办该种类型的画展，直到某一天他改办其他类型的画展为止。

在每一天，对于每一个画家 j，如果他举办画展，则他会参加自己举办的画展。如果这一天他自己不举办画展，则他希望去参加他认识的画家 Tj 在这天举办的画展。如果 Tj 这天也不举办画展，则他会跟着 Tj 去参加 Tj 希望参加的画展，依此类推。如果类推到最后也找不到当天可以参加的画展，那么他就会回家，这一天就不再参加画展了。

现在想要知道，在每一天，分别参加三种类型的画家各有多少人？

输入格式

第一行：一个整数 N

第二行：N 个整数 Ti

第三行：一个整数 M

接下来 M 行，每行一个整数 Pi (1 ≤ Pi ≤ N) 和一个大写字母 Ki (Ki ∈ { A, B, C })

输出格式

共 M 行，第 i 行包含三个整数，分别表示第 i 天分别参加 A, B, C 类型画展的人数，数与数之间以一个空格隔开。

输入样例

5
2 3 4 4 4
3
3 A
4 B
3 C

输出样例

3 0 0
3 2 0
0 2 3

数据范围

100% 的数据：$1 ≤ N, M ≤ 2×10^5$, $1 ≤ T_i, P_i ≤ N$, $K_i$ ∈ { A, B, C }。

• 其中 10% 的数据：$N, M ≤ 100$
• 另有 10% 的数据：$N, M ≤ 4000$
• 另有 25% 的数据：$T_i$ 是 $1$ ~ $N$ 的一个排列