TREASURE

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$ (lưu ý là không thể dùng chiếc chìa khóa thứ $i$ để mở cả hai rương $A_i$ và $B_i$). Mỗi chiếc rương chỉ có thể được mở khóa một lần, và không nhất thiết phải sử dụng tất cả các chìa khóa.

Cho $K$ truy vấn, truy vấn thứ $i$ yêu cầu bỏ đi chiếc chìa khóa thứ $P_i$ (các chìa khóa không được đánh số lại sau các truy vấn). Các truy vấn được thực hiện lần lượt, chìa khóa đã bỏ đi không được thêm lại.

Yêu cầu: Sau mỗi truy vấn, hãy cho biết: giả sử ta dùng các chìa khóa còn lại để mở rương, thì với cách mở khóa rương tối ưu, tổng giá trị kho báu lớn nhất thu được từ các rương được mở là bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên $N,K$ $(2\le N\le 200000,1\le K\le 200000)$, tương ứng là số rương kho báu và số chìa khóa; số chìa khóa đồng thời là số truy vấn.
• Dòng tiếp theo gồm $N$ số nguyên $C_1,C_2,\dots ,C_N$ $(1\le C_i\le {10}^9)$, là giá trị của các rương kho báu.
• $K$ dòng tiếp theo, dòng thứ $i$ 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ả chiếc chìa khóa thứ $i$. Hai chìa khóa khác nhau có thể mở cùng một cặp rương.
• Dòng tiếp theo gồm $K$ số nguyên phân biệt $P_1,P_2,\dots ,P_K$ $(1\le P_i\le K)$, mô tả các truy vấn.

Dữ liệu ra

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

Ràng buộc

• $2\le N\le 200000$, $1\le K\le 200000$.
• $1\le C_i\le {10}^9$.
• $1\le A_i,B_i\le N$, $A_i\ne B_i$.
• $P_1,P_2,\dots ,P_K$ đôi một phân biệt, $1\le P_i\le K$.

Subtasks

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

Ví dụ