Lýsing
Helloooo! Can you hear me?
Gefin er runa $A = (A_1, A_2, \dots, A_N)$ af lengd $N$ sem samanstendur af heiltölum sem eru stærri en eða jafnar $-1$. Með því að nota þessa runu og stika $c$ skal framkvæma eftirfarandi aðgerðir:
- Í upphafi skal setja breytuna $x := 0$.
- Fyrir $i = 1, 2, \dots, N$ skal endurtaka eftirfarandi aðgerð:
- Ef $A_i = -1$, uppfærðu $x$ í $x := \max(0, x - c)$.
- Annars, uppfærðu $x$ í $x := x + A_i$.
Svaraðu $Q$ spurningum á eftirfarandi formi:
- Þegar stikinn er $c = C_i$, finndu hæsta gildið sem $x$ nær yfir alla aðgerðarununa.
Inntak
Fyrsta línan inniheldur tvær heiltölur $N$ og $Q$ ($1 \le N, Q \le 3 \times 10^5$). Önnur línan inniheldur $N$ heiltölur $A_i$ ($-1 \le A_i \le 10^6$). Hver af næstu $Q$ línum inniheldur heiltölu $C_i$, sem táknar stikagildið fyrir $i$-tu spurninguna ($0 \le C_i \le 10^6$).
Úttak
Prentaðu $Q$ línur. Á $i$-tu línunni skal prenta svarið við $i$-tu spurningunni.
Dæmi
Inntak 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
Úttak 1
1700 1550 1400 950 570 500 500 850 500 500 1850
Athugasemd
Við útskýrum fyrstu spurninguna í fyrsta dæmainntakinu:
- Í þessari spurningu er stikinn $c = 30$.
- Í upphafi er $x = 0$.
- Þar sem $A_1 = 50$ uppfærist $x$ í $x = 0 + 50 = 50$.
- Þar sem $A_2 = 100$ uppfærist $x$ í $x = 50 + 100 = 150$.
- ...
- Þar sem $A_6 = 200$ uppfærist $x$ í $x = 300 + 200 = 500$.
- Þar sem $A_7 = -1$ uppfærist $x$ í $x = \max(0, 500 - 30) = 470$.
- ...
- Þar sem $A_{19} = -1$ uppfærist $x$ í $x = \max(0, 1530 - 30) = 1500$.
- Þar sem $A_{20} = 200$ uppfærist $x$ í $x = 1500 + 200 = 1700$.
Með úrfelldu hlutunum meðtöldum er hæsta gildið sem $x$ nær yfir alla aðgerðarununa $1700$.