Đi Dự Tiệc COW

Có $N$ con bò đánh số từ $1$ đến $N$, mỗi con có một bạn thân $a_i$. Trong $M$ đêm liên tiếp, các con bò tổ chức tiệc loại "C", "O", hoặc "W".

Mỗi đêm, khi bò $c_i$ tổ chức tiệc loại $v_i$, tiệc đó tồn tại cho đến khi một loại khác được tổ chức tại cùng bò đó. Các bò không tổ chức tiệc sẽ kiểm tra chuồng bạn thân. Nếu bạn thân không có tiệc, bò đi theo bạn thân (và bạn thân đó cũng đi theo bạn thân của mình, v.v.). Bò không thể đến tiệc nào sẽ bỏ cuộc.

Sau mỗi đêm, đếm số bò tham dự mỗi loại tiệc (C, O, W).

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• Dòng 2: $N$ số nguyên $a_1,a_2,\dots ,a_N$ (bạn thân)
• Dòng 3: Số nguyên $M$
• $M$ dòng tiếp theo: Số nguyên $c_i$ và ký tự $v_i$

Dữ liệu ra

• $M$ dòng, mỗi dòng gồm 3 số nguyên: số bò tham dự tiệc C, O, W.

Ràng buộc

• $1\le N,M\le 2\times {10}^5$
• $1\le a_i\le N$, $a_i\ne i$

Ví dụ