Giải bài trực tuyến

yenthanh132 hiện đang là giám đốc của Attosoft (micro = 10^-6, atto = 10^-18), công ty phần mềm lớn nhất vương quốc C11. Công ty có N nhân viên, được đánh số từ 1 đến N và yenthanh132 là người được đánh số 1. Mỗi người ngoại trừ yenthanh132 có đúng một sếp. Nếu z dưới quyền quản lí của nhân viên y và y dưới quyền quản lí của x thì z dưới quyền quản lí của x. Tất cả N-1 nhân viên còn lại trong công ty đều dưới quyền quản lí của yenthanh132.

Mỗi nhân viên trong công ty chuyên về một loại ngôn ngữ lập trình nhất định. Có tất cả M ngôn ngữ lập trình khác nhau được đánh số từ 1 đến M.

Mỗi khi nhận một đơn đặt hàng viết phần mềm gửi cho nhân viên u_i nào đó, nhân viên u_i này phải chọn ra trong số các nhân viên mà mình quản lí (kể cả mình), từ 1 đến K người cùng chuyên môn về một ngôn ngữ lập trình nào đó để viết phần mềm. Vấn đề đặt ra ở đây là yenthanh132 muốn biết xem với mỗi yêu cầu như vậy thì có bao nhiêu ngôn ngữ lập trình khác nhau mà trong số nhân viên u_i và các nhân viên mà u_i quản lí, có ít nhât một người và không quá K người chuyên môn về ngôn ngữ lập trình đó.

Yêu cầu:  Hãy giúp yenthanh132 trả lời xem nếu có một đơn đặt hàng gửi cho nhân viên u_i thì sẽ có bao nhiêu ngôn ngữ lập trình khác nhau thỏa điều kiện đã nêu ở trên

Input

• Dòng đầu tiên chứa 3 số nguyên N, M, K lần lượt là số nhân viên trong công ty, số lượng ngôn ngữ lập trình khác nhau, và số lượng nhân viên trong một cách chọn.
• N-1 dòng tiếp theo, dòng thứ i chứa số nguyên p_i+1 là sếp của nhân viên thứ i+1.
• Dòng thứ N+1 chứa N số nguyên v₁, v₂,... v_n. Trong đó v_i là ngôn ngữ lập trình chuyên môn của nhân viên i. (1 <= v_i <= M)
• Dòng thứ N+2 chứa số nguyên Q, là số truy vấn.
• Q dòng tiếp theo, dòng thứ i chứa số nguyên u_i (1 <= u_i <= N)

Output

• Gồm Q dòng, dòng thứ i là số ngôn ngữ lập trình khác nhau thỏa yêu cầu khi có một đơn đặt hàng gửi cho nhân viên u_i.

Giới hạn:

• Trong 20% số test có 1 <= N, Q, K <= 1000.
• Trong tất cả các test: 1 <= N, Q, K <= 10⁵
• 1 <= M <= 10⁵
• 1 <= K <= N

Example

Input:

10 4 2
1
2
2
3
3
1
7
7
7
1 2 4 3 2 4 4 3 3 3
4
1
2
7
3

Output:

2
3
1
2