Beskrivning
Helloooo! Can you hear me?
Du får en följd $A = (A_1, A_2, \dots, A_N)$ av längd $N$ som består av heltal större än eller lika med $-1$. Med hjälp av denna följd och en parameter $c$, utför följande operationer:
- Sätt initialt variabeln $x := 0$.
- För $i = 1, 2, \dots, N$, upprepa följande operation:
- Om $A_i = -1$, uppdatera $x$ till $x := \max(0, x - c)$.
- Annars, uppdatera $x$ till $x := x + A_i$.
Besvara $Q$ frågor av följande form:
- När parametern är $c = C_i$, hitta det största värdet som $x$ antar under hela operationsföljden.
Indata
Den första raden innehåller två heltal $N$ och $Q$ ($1 \le N, Q \le 3 \times 10^5$). Den andra raden innehåller $N$ heltal $A_i$ ($-1 \le A_i \le 10^6$). Var och en av de följande $Q$ raderna innehåller ett heltal $C_i$, som representerar parametervärdet för den $i$-te frågan ($0 \le C_i \le 10^6$).
Utdata
Skriv ut $Q$ rader. På den $i$-te raden, skriv ut svaret på den $i$-te frågan.
Exempel
Indata 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
Utdata 1
1700 1550 1400 950 570 500 500 850 500 500 1850
Anmärkning
Vi förklarar den första frågan i det första exemplets indata:
- I denna fråga är parametern $c = 30$.
- Initialt är $x = 0$.
- Eftersom $A_1 = 50$ uppdateras $x$ till $x = 0 + 50 = 50$.
- Eftersom $A_2 = 100$ uppdateras $x$ till $x = 50 + 100 = 150$.
- ...
- Eftersom $A_6 = 200$ uppdateras $x$ till $x = 300 + 200 = 500$.
- Eftersom $A_7 = -1$ uppdateras $x$ till $x = \max(0, 500 - 30) = 470$.
- ...
- Eftersom $A_{19} = -1$ uppdateras $x$ till $x = \max(0, 1530 - 30) = 1500$.
- Eftersom $A_{20} = 200$ uppdateras $x$ till $x = 1500 + 200 = 1700$.
Inklusive de utelämnade delarna är det största värdet som $x$ antar under hela operationsföljden $1700$.