Năm nay An được thầy chọn đi dự thi Học sinh giỏi Duyên Hải môn Tin học tại Ninh Bình. Nơi được ví là Hạ Long trên cao, có bề dày lịch sử đầy tự hào của dân tộc và cũng có hệ sinh thái đa dạng và phong phú.

Sau khi tham quan cố đô Hoa Lư nghe lịch sử dân tộc, An được các thầy cho đi tham quan hệ sinh thái tại vườn quốc gia Vân Long (cách trung tâm thành phố Ninh Bình 17 km về phía Đông Bắc), An rất vui vì được thỏa mong ước bấy lâu nay - nghiên cứu về loài chuồn chuồn.

Chuồn chuồn có thể được nhìn thấy xung quanh các ao ở Vườn quốc gia Vân Long. Ở một trong những khu vực rừng rậm rạp, An đã ghi lại ~n~ ao mà chuồn chuồn bay xung quanh. Tại ao thứ ~i~ (~1 \le i \le n~), có ~b_i~ con bọ mà chuồn chuồn có thể ăn. Các loài bọ ở ao thứ ~i~ thuộc loài ~s_i~.

An cũng đã ghi lại ~n - 1~ đường mòn. Mỗi đường mòn ~j~ (~1 \le j < n~) kết nối 2 ao riêng biệt ~u_j~ và ~v_j~ theo hai chiều. Chuồn chuồn có thể di chuyển từ bất kỳ ao nào đến bất kỳ ao nào khác chỉ bằng cách sử dụng các đường mòn.

An đã bắt được ~d~ con chuồn chuồn và dự định thả chúng lần lượt tại ao 1. Chuồn chuồn thứ ~k~ (~1 \le k \le d~) có ao nhà là ~h_k \ne 1~ và sẽ di chuyển đến ao ~h_k~ mà không ghé thăm bất kỳ ao nào nhiều hơn một lần chỉ bằng cách sử dụng các đường mòn. Những con chuồn chuồn này sẽ được thả theo thứ tự tăng dần từ chuồn chuồn 1 đến chuồn chuồn ~d~. Sau khi một con chuồn chuồn được thả, nó sẽ ăn một con bọ duy nhất (nếu còn một hoặc nhiều con bọ) tại mỗi ao mà nó ghé thăm (bao gồm cả ao 1), giảm số lượng bọ tại mỗi ao đó đi 1 (nếu ban đầu số bọ không phải là 0).

Yêu cầu: Xác định số lượng các loài bọ riêng biệt đã bị ăn trong suốt hành trình của mỗi con chuồn chuồn từ con thứ 1 tới ~d~.

Input

• Dòng đầu chứa 2 số nguyên cách nhau ~n, d~ (~2 \le n \le 2 \cdot 10^5~; ~1 \le d \le 2 \cdot 10^5~);
• Dòng tiếp theo chứa ~n~ số nguyên ~b_1, b_2, \dots, b_n~ (~0 \le b_i \le d~);
• Dòng tiếp theo chứa ~n~ số nguyên ~s_1, s_2, \dots, s_n~ (~1 \le s_i \le n~);
• Dòng tiếp theo chứa ~d~ số nguyên ~h_1, h_2, \dots, h_d~ (~2 \le h_k \le n~);
• ~n - 1~ dòng tiếp theo, dòng thứ ~j~ trong số các dòng này chứa ~u_j, v_j~ (~1 \le u_j, v_j \le n~; ~u_j \ne v_j~).

Output

• Ghi ra một dòng duy nhất gồm ~d~ số nguyên. Số nguyên thứ ~k~ trong số các số nguyên này phải là số loài bọ riêng biệt bị con chuồn chuồn thứ ~k~ ăn.