Deskripsi
Helloooo! Can you hear me?
Anda diberikan sebuah barisan $A = (A_1, A_2, \dots, A_N)$ sepanjang $N$ yang terdiri dari bilangan bulat lebih besar dari atau sama dengan $-1$. Dengan menggunakan barisan ini dan sebuah parameter $c$, lakukan operasi berikut:
- Pada awalnya, atur variabel $x := 0$.
- Untuk $i = 1, 2, \dots, N$, ulangi operasi berikut:
- Jika $A_i = -1$, perbarui $x$ menjadi $x := \max(0, x - c)$.
- Jika tidak, perbarui $x$ menjadi $x := x + A_i$.
Jawablah $Q$ pertanyaan dengan bentuk berikut:
- Ketika parameter $c = C_i$, carilah nilai maksimum yang dicapai oleh $x$ selama seluruh rangkaian operasi.
Masukan
Baris pertama berisi dua bilangan bulat $N$ dan $Q$ ($1 \le N, Q \le 3 \times 10^5$). Baris kedua berisi $N$ bilangan bulat $A_i$ ($-1 \le A_i \le 10^6$). Masing-masing dari $Q$ baris berikutnya berisi sebuah bilangan bulat $C_i$, yang menyatakan nilai parameter untuk pertanyaan ke-$i$ ($0 \le C_i \le 10^6$).
Keluaran
Cetak $Q$ baris. Pada baris ke-$i$, cetak jawaban untuk pertanyaan ke-$i$.
Contoh
Masukan 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
Keluaran 1
1700 1550 1400 950 570 500 500 850 500 500 1850
Catatan
Berikut adalah penjelasan untuk pertanyaan pertama pada masukan contoh pertama:
- Pada pertanyaan ini, parameternya adalah $c = 30$.
- Pada awalnya, $x = 0$.
- Karena $A_1 = 50$, $x$ diperbarui menjadi $x = 0 + 50 = 50$.
- Karena $A_2 = 100$, $x$ diperbarui menjadi $x = 50 + 100 = 150$.
- ...
- Karena $A_6 = 200$, $x$ diperbarui menjadi $x = 300 + 200 = 500$.
- Karena $A_7 = -1$, $x$ diperbarui menjadi $x = \max(0, 500 - 30) = 470$.
- ...
- Karena $A_{19} = -1$, $x$ diperbarui menjadi $x = \max(0, 1530 - 30) = 1500$.
- Karena $A_{20} = 200$, $x$ diperbarui menjadi $x = 1500 + 200 = 1700$.
Termasuk bagian yang dihilangkan, nilai maksimum yang dicapai oleh $x$ selama seluruh rangkaian operasi adalah $1700$.