Khu rừng có ~N~ cây, cây thứ ~j~ có lượng gỗ ~v_j~. Có ~P~ phương án, phương án thứ ~i~ chọn khai thác tất cả các cây có lượng gỗ từ ~k_i~ trở lên.

Yêu cầu

Với mỗi phương án, tính tổng lượng gỗ khai thác được.

Input

Dòng đầu chứa ~N~ ~(1 < N \le 10^6)~.

Dòng thứ hai chứa ~N~ số ~v_j~ ~(1 \le v_j \le 10^6)~.

Dòng thứ ba chứa ~P~ ~(1 \le P \le 10^5)~.

Dòng cuối chứa ~P~ số ~k_i~ ~(1 \le k_i \le 10^6)~.

Output

In ra ~P~ dòng, dòng thứ ~i~ là tổng lượng gỗ của phương án thứ ~i~.

Subtask

• Có 40% số điểm có ~P=1~.
• Có 30% số điểm có ~2 \le N,P \le 1000~.
• Có 30% số điểm còn lại không có ràng buộc bổ sung.

Ví dụ 1

5
1 2 3 4 5
1
4

9

Ví dụ 2

5
1 10 4 5 2
2
4 5

19
15