Vasa sakupljac aura

Vendelnek 0 aurája van, és ez neki nem tetszik.

Ezért úgy döntött, hogy egy tömbön történő végighaladással aurát gyűjt. Formálisan egy k hosszúságú b egész számokat tartalmazó tömb esetén Vendel az i = 1 indexről indul a = 0 aurával és c = 1 együtthatóval. Ezt követően végighalad a tömbön, és sorban gyűjti az elemek auráját úgy, hogy az aurájához hozzáadja a c \cdot b_i értéket. Miután összegyűjtötte az i-edik elem auráját, megnövelheti a c értékét eggyel.

Természetesen Vendel maximalizálni szeretné az auráját a teljes tömb bejárásával (figyeljük meg, hogy ez az érték akár negatív is lehet). Továbbá Vendel azt szeretné, hogy a bejárás végén a c értéke pontosan x legyen.

Adott egy p tömb n elemmel. Írjátok ki, mennyi aurát tud Vendel gyűjteni minden pontosan k hosszúságú b résztömb esetén. Vegyétek észre, hogy ezek a gyűjtések egymástól függetlenül történnek.

Bemenet leírása

A szabványos bemenet első sorában három egész szám szerepel: n – a p tömb hossza, k – azoknak a résztömböknek a hossza, amelyeken Vendel aurát gyűjt, valamint x – a c együttható végső értéke.

A szabványos bemenet második sorában n egész szám található. Az i-edik közülük p_i, és a p tömb i-edik elemének értékét jelöli.

Kimenet leírása

A szabványos kimenet első sorába írjátok ki n-k+1 számot, amelyek a p tömb minden k hosszúságú résztömbjére a maximálisan elérhető aura értékét jelentik.

1. példa

Bemenet

5 3 2
1 -2 4 4 -5

Kimenet

7 14 3

A példa magyarázata

Pontosan három darab k = 3 hosszúságú résztömb van:

• [1, -2, 4] – Vendel a második elem begyűjtése után növeli c-t 1-ről 2-re, így a végső aurája 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] – Vendel az első elem begyűjtése után növeli c-t 1-ről 2-re, így a végső aurája 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] – Vendel a harmadik elem begyűjtése után növeli c-t 1-ről 2-re, így a végső aurája 1 \cdot b_1 + 1 \cdot b_2 + 1\cdot b_3 = 1 \cdot 4 + 1 \cdot 4 - 1 \cdot 5 = 3.

2. példa

Bemenet

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

Kimenet

-12 -9 4 23

Korlátozások

• 1 \leq x \leq k \leq n \leq 200.000.
• |p_i| \leq 10^9 minden 1 \leq i \leq n-re.

A tesztpéldák hat diszjunkt csoportba vannak sorolva:

• A 10 pontot érő tesztpéldákban: érvényes, hogy n \leq 20
• A 10 pontot érő tesztpéldákban: érvényes, hogy p_i \geq 0; 1 \leq i \leq n-re.
• A 15 pontot érő tesztpéldákban: érvényes, hogy n \leq 300.
• A 15 pontot érő tesztpéldákban: érvényes, hogy n \leq 3.000.
• A 10 pontot érő tesztpéldákban: érvényes, hogy x = 2.
• A 30 pontot érő tesztpéldákban: nincsenek további korlátozások.