Gấu đang chuẩn bị một bữa tiệc cho bạn bè của mình. Bữa tiệc bao gồm ~n~ đĩa thức ăn được xếp thành một hàng, đĩa thứ ~i~ tính từ đầu bên trái cho ~a_i~ điểm hài lòng nếu được ăn. Một số đĩa thức ăn không ngon, nên điểm ~a_i~ có thể bằng ~0~ hoặc bằng số âm.

Có ~k~ người tham gia bữa tiệc và mỗi người sẽ được giao một đoạn đĩa liên tiếp để ăn, đoạn này có thể trống. Các đoạn của hai người không được giao nhau, vì thức ăn không thể ăn hai lần. Gấu muốn phân bổ các đĩa thức ăn cho bạn bè của mình sao cho tổng điểm hài lòng của tất cả các đĩa thức ăn được phân bổ là tối đa.

Vì số bạn bè rất đông (do Gấu là một người tốt tính, tốt bụng, hài hước, vui vẻ, đẹp trai...) nên anh ta không thể mời tất cả bạn dự tiệc một ngày, do đó bữa tiệc sẽ diễn ra trong ~q~ ngày, vào ngày ~i~, Gấu sẽ mời ~k_i~ bạn đến dự. Hãy giúp Gấu tìm tổng điểm hài lòng lớn nhất cho ~q~ ngày này nhé.

Dữ liệu:

Vào từ tệp văn bản feas.inp.

• Dòng đầu tiên chứa hai số nguyên ~n, q~ ~(1 \leq n, q \leq 5*10^5)~.
• Dòng hai chứa $n$ số nguyên ~a_i~ mô tả bàn tiệc của Gấu ~(0 \leq |a_i| \leq 10^9)~.
• Dòng ba chứa $q$ số nguyên mô tả số bạn bè trong ~q~ ngày diễn ra tiệc ~(1 \leq k_i \leq n)~.

Kết quả:

Ghi ra tệp văn bản feas.out.

Gồm một dòng chứa ~q~ số nguyên là đáp án cho ~q~ câu hỏi.

Ví dụ

Input

5 3
1 -1 2 -2 3
1 2 5

Output

3 5 6

Note

• Với $k = 1$, Gấu sẽ chọn dĩa thứ ~5~ cho bạn.
• Với ~k = 2~, Gấu sẽ chọn hai dĩa thứ ~3, 5~ cho hai bạn.
• Với ~k = 5~, Gấu sẽ chọn ba dĩa ~1, 3, 5~ cho ba bạn, hai bạn còn lại sẽ nhìn Gấu ăn :>

Tính điểm

• Subtask 1 (20% số điểm): ~Q = 1, K = 1~.
• Subtask 2 (20% số điểm): ~Q = 1, K \leq 2~.
• Subtask 3 (20% số điểm): ~Q = 1, K \leq 50~.
• Subtask 4 (20% số điểm): ~Q = 1~.
• Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.