문제

민수가 회장으로 있는 알고리즘 동아리 ANA에는 $1$번부터 $N$번까지 번호가 매겨진 $N$명의 부원이 있다. ($1 eq N eq 200\,000$) 각 부원 $i$는 자신만의 개인 연습실을 가지고 있으며, 가장 친한 친구 $a_i$가 한 명씩 있다. ($1 \le a_i \le N$) 가장 친한 친구는 자기 자신일 수도 있으며, 여러 부원이 같은 사람을 가장 친한 친구로 생각할 수도 있다. 부원들은 모임을 즐기기 때문에, $M$일 ($1 \le M \le 200\,000$) 동안 매일 밤 모임을 열기로 했다.

$i$번째 날 밤에, 부원 $c_i$는 자신의 연습실에서 $t_i$ 타입의 모임을 열기로 결정한다. ($t_i \in \{ `C`, `O`, `W` \}$) 이 모임은 부원 $c_i$가 다른 타입의 모임을 새로 열 때까지 이후의 모든 밤에도 계속 유지된다.

매일 밤, 모든 부원은 다음 규칙에 따라 하나의 모임에 참여하려고 시도한다:

1. 만약 자신이 현재 모임을 열고 있다면, 자신의 연습실에서 열리는 모임에 참여한다.
2. 자신이 모임을 열고 있지 않다면, 가장 친한 친구의 연습실을 확인한다. 그곳에 모임이 있다면 그 모임에 참여한다.
3. 친구의 연습실에도 모임이 없다면, 친구가 참여하러 가는 곳을 그대로 따라간다. (친구 역시 자신의 친구를 따라갈 수 있다.)
4. 만약 이 과정을 반복해도 모임을 찾지 못한다면(예: 친구 관계를 따라가다 순환이 발생했지만 그들 중 아무도 모임을 열지 않은 경우), 그날 밤은 모임에 참여하는 것을 포기한다.

매일 밤, C, O, W 각 타입의 모임에 참여하는 부원의 수를 각각 구하시오.

입력

첫째 줄에 부원의 수 $N$이 주어진다.

둘째 줄에 각 부원의 가장 친한 친구 번호 $a_1, a_2, \dots, a_N$이 공백으로 구분되어 주어진다.

셋째 줄에 모임이 열리는 기간 $M$이 주어진다.

이어서 $M$개의 줄에 걸쳐, $i$번째 날 밤에 모임을 여는 부원의 번호 $c_i$와 모임의 타입 $v_i$가 공백으로 구분되어 주어진다. ($1 \le c_i \le N$; $v_i \in \{ `C`, `O`, `W` \}$)

출력

$M$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 날 밤에 C, O, W 타입의 모임에 참여한 부원의 수를 공백으로 구분하여 순서대로 출력한다.

제한

• 서브태스크 1: $N, M \le 100$
• 서브태스크 2: $N, M \le 4\,000$
• 서브태스크 3: $\{a_i\}$는 $1$부터 $N$까지의 수로 이루어진 순열이다.
• 서브태스크 4: 추가 제약 조건이 없다.

예제 입력 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