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 ý rằng 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.

Có ~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. Sau mỗi truy vấn, giả sử sử dụng các chìa khóa còn lại để mở rương, hãy tìm tổng giá trị kho báu lớn nhất có thể thu được từ các rương được mở.

Input

• Dòng đầu tiên gồm hai số nguyên ~N, K~ ~(2 \le N \le 200000, 1 \le K \le 200000)~, lần lượt 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~;

• 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.

Output

Gồm ~K~ dòng, dòng thứ ~i~ chứa 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~.

Scoring

Sample Input 1

4 4
9 5 7 2
2 3
3 1
1 2
1 4
4 1 2 3

Sample Output 1

21
16
9
0

Notes

• Sau truy vấn thứ nhất, còn lại các chìa khóa ~1, 2, 3~. Có thể dùng chìa khóa ~1~ để mở rương ~2~, chìa khóa ~2~ để mở rương ~3~ và chìa khó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, còn lại các chìa khóa ~2, 3~. Có thể dùng chìa khóa ~2~ để mở rương ~3~ và chìa khóa ~3~ để mở rương ~1~. Tổng giá trị của các rương được mở là ~9 + 7 = 16~;

• Sau truy vấn thứ ba, chỉ còn lại chìa khóa ~3~. Dùng chìa khóa này để mở rương ~1~ với giá trị ~9~;

• Sau truy vấn thứ tư, không còn chiếc chìa khóa nào nên không mở được bất kỳ rương kho báu nào.