Có $N$ chiếc rương kho báu, chiếc rương thứ $i$ có giá trị là $C_i$. Ban đầu, có $K$ chìa khóa.
Chiếc chìa khóa thứ $i$ có thể được dùng để mở một trong hai chiếc rương $A_i$ và $B_i$ ($A_i\ne B_i$).
Mỗi chiếc rương chỉ có thể mở bằng một chìa khóa, và không nhất thiết phải sử dụng hết tất cả các chìa khóa.

Yêu cầu:

Cho $K$ truy vấn, truy vấn thứ $i$ yêu cầu mở được chiếc khóa thứ $P_i$ (các chìa khóa không được đánh số lại sau các truy vấn). Sau mỗi truy vấn, hãy cho biết:
Giá trị tối đa của kho báu có thể mở được, nếu với cách mở khóa rương tối ưu, trong giải pháp lớn nhất ưu tiên được mở các rương có giá trị bảo nhiều nhất.

Dữ liệu vào

Tệp tin TREASURE.INP gồm:

• Dòng đầu tiên gồm ba số nguyên $N,K$ ($2\le N\le 200000,1\le K\le 200000$)
  tương ứng là số lượng rương kho báu, số chìa khóa đang có và số truy vấn.
• Dòng tiếp theo, gồm $N$ số nguyên $C_1,C_2,...,C_N$ ($1\le C_i\le {10}^9$) - giá trị của các rương kho báu.
• $K$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $A_i,B_i$ ($1\le A_i,B_i\le N,A_i\ne B_i$) - mô tả các chiếc chìa khóa.
• Dòng tiếp theo, gồm $K$ số nguyên phân biệt $P_1,P_2,...,P_K$ ($1\le P_i\le K$) - mô tả các truy vấn.

Kết quả

Ghi ra tệp TREASURE.OUT $K$ dòng,
mỗi dòng gồm một số nguyên là giá trị kho báu lớn nhất thu được sau khi thực hiện truy vấn thứ $i$.

Ví dụ

Input 4 4

9 5 7 2

2

3

1

1 4

4 1 2 3

Output

21

16

9

0

Giải thích

• Sau truy vấn thứ nhất, còn lại các chìa khóa $1,2,3$. Ta có thể dùng chìa $1$ để mở rương $2$, chìa $2$ để mở rương $3$ và chìa $3$ để mở rương $1$. Tổng giá trị của các rương được mở là $9+5+7=21$.
• Sau truy vấn thứ hai, chỉ còn các chìa khóa $2,3$. Ta có thể mở các rương $2$ và $3$, tổng giá trị là $5+7=12$.
• Sau truy vấn thứ ba, chỉ còn chìa khóa $3$. Ta chỉ có thể mở rương $3$ có giá trị $7$.
• Sau truy vấn thứ tư, không còn chìa khóa nào nên không mở được bất kì rương nào => kết quả $0$.

Các giới hạn

• Sub 1 (30% số điểm): $N,K\le 16$
• Sub 2 (30% số điểm): $N,K\le 3000$
• Sub 3 (40% số điểm): không có ràng buộc gì thêm.