Có N chiếc rương kho báu, chiếc rương thứ i có giá trị là Ci. 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 Ai và Bi (lưu ý là không thể dùng chiếc chìa thứ i để mở cả hai rương Ai và Bi). 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ứ Pi (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ả 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

• Dòng đầu tiên gồm ba số nguyên N, K (2 ≤ N ≤ 200000, 1 ≤ K ≤ 200000) — số rương kho báu, số chìa khóa đồng thời là số truy vấn.

• Dòng tiếp theo, gồm N số nguyên C1, C2, . . . , CN (1 ≤ Ci ≤ 10^9) — 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 Ai và Bi (1 ≤ Ai, Bi ≤ N, Ai ≠Bi) — 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 P1, P2, . . . , PK (1 ≤ Pi ≤ K) — mô tả các truy vấn.

Kết quả

In ra 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.

Sample Input

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

Sample Output

21
16
9
0

Ràng buộc:

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