Helloooo! Can you hear me?

Bạn được cho một dãy số $A = (A_1, A_2, \dots, A_N)$ có độ dài $N$ bao gồm các số nguyên lớn hơn hoặc bằng $-1$. Sử dụng dãy số này và một tham số $c$, hãy thực hiện các thao tác sau:

• Ban đầu, đặt biến $x := 0$.

• Với $i = 1, 2, \dots, N$, lặp lại thao tác sau:

  • Nếu $A_i = -1$, thay thế $x$ bằng $x := \max(0, x - c)$.
  • Nếu không, thay thế $x$ bằng $x := x + A_i$.

Hãy trả lời $Q$ câu hỏi có dạng sau:

• Khi tham số $c = C_i$, hãy tìm giá trị lớn nhất mà $x$ đạt được trong toàn bộ quá trình thực hiện các thao tác.

Dữ liệu vào

Dòng đầu tiên chứa $N, Q$ theo thứ tự đó. ($1 \le N, Q \le 3 \times 10^5$) Dòng thứ hai chứa $N$ số nguyên $A_i$. ($-1 \le A_i \le 10^6$) Mỗi dòng trong số $Q$ dòng tiếp theo chứa giá trị $C_i$ cho câu hỏi thứ $i$. ($0 \le C_i \le 10^6$)

Dữ liệu ra

In ra $Q$ dòng. Trên dòng thứ $i$, in ra câu trả lời cho câu hỏi thứ $i$.

Ví dụ

Dữ liệu vào 1

20 11
50 100 50 100 0 200 -1 50 100 -1 200
-1 200 0 200 -1 200 200 -1 200
30
60
90
180
270
360
540
200
400
600
0

Dữ liệu ra 1

1700
1550
1400
950
570
500
500
850
500
500
1850

Ghi chú

Chúng tôi giải thích câu hỏi đầu tiên của ví dụ trên.

• Trong câu hỏi này, tham số là $c = 30$.
• Ban đầu, biến $x = 0$.
• Vì $A_1 = 50$, $x$ được cập nhật thành $x = 0 + 50 = 50$.
• Vì $A_2 = 100$, $x$ được cập nhật thành $x = 50 + 100 = 150$.
• ...
• Vì $A_6 = 200$, $x$ được cập nhật thành $x = 300 + 200 = 500$.
• Vì $A_7 = -1$, $x$ được cập nhật thành $x = \max(0, 500 - 30) = 470$.
• ...
• Vì $A_{19} = -1$, $x$ được cập nhật thành $x = \max(0, 1530 - 30) = 1500$.
• Vì $A_{20} = 200$, $x$ được cập nhật thành $x = 1500 + 200 = 1700$.

Bao gồm cả các phần đã lược bỏ, giá trị lớn nhất mà $x$ đạt được trong toàn bộ quá trình thực hiện các thao tác là $1700$.