C11COMP - VNOI

C11COMP - Quản lí công ty 2

Giới hạn

Thời gian: 1.0s
Bộ nhớ: 1536MB
Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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:

Người up: yenthanh132