Đ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 thứ $i$, bò $c_i$ tổ chức tiệc loại $v_i$. Kể từ đêm đó trở đi, chuồng của bò $c_i$ luôn có tiệc: loại tiệc tại đó giữ nguyên là $v_i$ cho đến khi chính bò $c_i$ tổ chức một loại khác. Bò tổ chức tiệc thì tham dự chính tiệc của mình.

Mỗi đêm, 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 (do chuỗi bạn thân quay thành vòng mà không gặp tiệc nào) sẽ bỏ cuộc và không tham dự tiệc nào.

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

• $2\le N\le 2\times {10}^5$
• $1\le M\le 2\times {10}^5$
• $1\le a_i\le N$, $a_i\ne i$
• $1\le c_i\le N$, $v_i\in \{$C, O, W$\}$

Ví dụ