Dragonfly

Chuồn chuồn thường xuất hiện quanh các ao ở Vườn Bách thảo và Công viên Bishan. Trong một khu rừng rậm, thỏ Benson ghi nhận có ~n~ ao mà chuồn chuồn bay qua. Tại ao ~i~ (~1 \le i \le n~), có ~b_i~ con côn trùng thuộc loài ~s_i~ mà chuồn chuồn có thể ăn.

Benson cũng ghi nhận ~n-1~ con đường mòn. Đường thứ ~j~ nối hai ao phân biệt ~u_j~ và ~v_j~ theo cả hai chiều. Từ mỗi ao đều có thể đi đến mọi ao khác chỉ bằng các đường mòn này.

Benson bắt được ~d~ con chuồn chuồn và sẽ lần lượt thả chúng tại ao ~1~. Con thứ ~k~ (~1 \le k \le d~) có ao nhà là ~h_k \ne 1~ và bay tới ~h_k~ theo các đường mòn mà không ghé thăm ao nào quá một lần. Các con chuồn chuồn được thả theo thứ tự từ ~1~ đến ~d~.

Khi bay qua mỗi ao (kể cả ao ~1~), chuồn chuồn ăn đúng một con côn trùng nếu ao đó vẫn còn côn trùng; khi đó số côn trùng tại ao giảm đi ~1~.

Hãy xác định số loài côn trùng khác nhau mà mỗi con chuồn chuồn ăn được trong hành trình của nó.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~d~.
• Dòng tiếp theo gồm ~n~ số nguyên ~b_1,b_2,\ldots,b_n~.
• Dòng tiếp theo gồm ~n~ số nguyên ~s_1,s_2,\ldots,s_n~.
• Dòng tiếp theo gồm ~d~ số nguyên ~h_1,h_2,\ldots,h_d~.
• ~n-1~ dòng cuối, dòng thứ ~j~ gồm hai số nguyên ~u_j~ và ~v_j~.

Dữ liệu ra

In ra một dòng gồm ~d~ số nguyên. Số thứ ~k~ là số loài côn trùng khác nhau mà con chuồn chuồn thứ ~k~ đã ăn.

Giới hạn

• ~2 \le n \le 2 \cdot 10^5~
• ~1 \le d \le 2 \cdot 10^6~
• ~1 \le s_i \le n~
• ~0 \le b_i \le d~
• ~1 \le u_j,v_j \le n~ và ~u_j \ne v_j~
• ~2 \le h_k \le n~

Ví dụ 1

Input

5 6
4 1 0 3 1
1 3 2 2 1
2 5 4 3 4 2
5 2
2 1
1 4
1 3

Output

2 1 2 1 1 0

Ví dụ 2

Input

7 4
0 2 4 4 0 1 3
6 1 6 2 2 2 1
7 5 2 4
4 1
4 5
6 2
1 6
1 3
6 7

Output

2 1 1 1

Nguồn: NOI Singapore 2022 Qualification, Task 3.