Vasa sakupljac aura

Vasa ima 0 aure. Vasi se to ne sviđa.

Zato je odlučio skupljati auru prolaskom kroz nisku. Formalno, za danu nisku cijelih brojeva b dužine k, Vasa kreće od indeksa i = 1 s aurom a = 0 i koeficijentom c = 1. Nakon toga on prolazi kroz nisku i redom skuplja aure elemenata tako što dodaje na svoju auru vrijednost c \cdot b_i. Nakon što sakupi auru elementa i, on može povećati vrijednost c za jedan.

Prirodno, Vasa želi u najvećoj mjeri povećati auru koju ima nakon prolaska kroz cijelu nisku (primijetite da ova vrijednost može biti i negativna). Dodatno, Vasa želi da nakon prolaska kroz nisku vrijednost c bude točno x.

Dana je niska p s n elemenata. Ispisati auru koju Vasa može sakupiti za svaku podnisku b dužine točno k. Primijetite kako se ova sakupljanja odigravaju neovisno.

Opis ulaza

U prvom retku su dana tri cijela broja n - dužina niske p, k - dužine podniski na kojima će Vasa skupljati auru, i x - krajnja vrijednost koeficijenta c.

U drugoj liniji standardnog ulaza, dano je n cijelih brojeva. i-ti od njih je p_i i predstavlja vrijednost i-tog elementa niske p.

Opis izlaza

U prvoj liniji ispisati n-k+1 brojeva, koji predstavljaju najveću vrijednost aure za svaku podnisku dužine k niske p.

Primjer 1

Ulaz

5 3 2
1 -2 4 4 -5

Izlaz

7 14 3

Objašnjenje primjera 1

Postoje tri podniske dužine točno k = 3:

• [1, -2, 4] - Vasa će povećati c s 1 na 2 nakon sakupljanja drugog elementa niske, pa je njegova konačna aura 1 \cdot b_1 + 1 \cdot b_2 + 2\cdot b_3 = 1 \cdot 1 - 1 \cdot 2 + 2\cdot 4 = 7.
• [-2, 4, 4] - Vasa će povećati c s 1 na 2 nakon sakupljanja prvog elementa niske, pa je njegova konačna aura 1 \cdot b_1 + 2 \cdot b_2 + 2\cdot b_3 = - 1 \cdot 2 + 2 \cdot 4 + 2\cdot 4 = 14.
• [4, 4, -5] - Vasa će povećati c s 1 na 2 nakon sakupljanja trećeg elementa niske, pa je njegova konačna aura 1 \cdot b_1 + 1 \cdot b_2 + 1\cdot b_3 = 1 \cdot 4 + 1 \cdot 4 - 1 \cdot 5 = 3.

Primjer 2

Ulaz

7 4 3
-10 2 2 -5 -4 5 7

Izlaz

-12 -9 4 23

Ograničenja

• 1 \leq x \leq k \leq n \leq 200.000.
• |p_i| \leq 10^9 za svako 1 \leq i \leq n.

Test primjeri su podijeljeni u 6 disjunktnih skupina:

• U testovima vrijednim 10 bodova: važi n \leq 20
• U testovima vrijednim 10 bodova: važi p_i \geq 0, за 1 \leq i \leq n.
• U testovima vrijednim 15 bodova: važi n \leq 300.
• U testovima vrijednim 15 bodova: važi n \leq 3.000.
• U testovima vrijednim 20 bodova: važi x = 2.
• U testovima vrijednim 30 bodova: bez dodatnih ograničenja.