Có \(N\) (\(1\le N\le 2\cdot 10^5\)) con bò được đánh số \(1\dots N\) trong trang trại của Farmer John, mỗi con bò sống trong một chuồng riêng. Mỗi con bò \(i\) có một người bạn thân nhất \(a_i\) (\(1\le a_i\le N\)). Một con bò có thể là bạn thân nhất của chính nó, và nhiều con bò có thể có cùng một người bạn thân nhất. Những con bò rất thích tiệc tùng, vì vậy chúng quyết định tổ chức tiệc trong \(M\) (\(1\le M\le 2\cdot 10^5\)) đêm liên tiếp.

Vào đêm thứ \(i\), bò \(c_i\) sẽ quyết định tổ chức một bữa tiệc loại \(t_i\) tại chuồng của mình, với \(t_i\in \texttt{"COW"}\). Bữa tiệc này cũng sẽ tồn tại trong tất cả các đêm sau đó, cho đến khi bò \(c_i\) quyết định tổ chức một bữa tiệc thuộc loại khác.

Mỗi đêm, mỗi con bò sẽ cố gắng đi đến một bữa tiệc. Nếu một con bò không tổ chức tiệc, nó sẽ kiểm tra chuồng của người bạn thân nhất; nếu ở đó không có tiệc, nó sẽ đi theo người bạn thân nhất đến bất cứ nơi nào người bạn ấy đang đi (người bạn này cũng có thể đi theo bạn thân nhất của mình, và cứ tiếp tục như vậy). Có thể một con bò không bao giờ tìm thấy bữa tiệc nào và khi đó sẽ bỏ cuộc trong đêm ấy.

Với mỗi đêm, hãy tính số bò cuối cùng đến dự bữa tiệc loại \(C\), \(O\) và \(W\), theo thứ tự đó.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), số lượng bò.

Dòng thứ hai chứa \(a_1,\dots,a_N\), trong đó \(a_i\) là người bạn thân nhất của bò \(i\).

Dòng thứ ba chứa \(M\), số lượng đêm.

\(M\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(c_i\) (\(1\le c_i\le N\)) và một ký tự \(v_i\), lần lượt biểu thị con bò tổ chức tiệc và loại của bữa tiệc.

Dữ liệu ra

In ra \(M\) dòng, trong đó dòng thứ \(i\) gồm \(3\) số nguyên cách nhau bởi dấu cách, lần lượt là số bò đi đến các bữa tiệc loại \(C\), \(O\) và \(W\) trong đêm thứ \(i\).

Ví dụ

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

2 0 0
5 0 0
2 0 3
0 2 3

Phân nhóm

• Dữ liệu vào 2: \(N,M\leq 100\).
• Dữ liệu vào 3–4: \(N,M\leq 4000\).
• Dữ liệu vào 5–9: \(\{a_i\}\) là một hoán vị của \(\{1,\dots,N\}\).
• Dữ liệu vào 10–21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 1, Gold Division — “COW Traversals”. Tác giả đề: Benjamin Qi. https://usaco.org/index.php?page=viewproblem2&cpid=1545