Vasa sakupljac aura

Васа има 0 ауре. Васи се то не свиђа.

Зато је одлучио да скупља ауру проласком кроз низ. Формално, за дати низ целих бројева b дужине k, Васа креће од индекса i = 1 са ауром a = 0 и коефцијентом c = 1. Потом он пролази кроз низ и редом скупља ауре елемената тако што додаје на своју ауру вредност c \cdot b_i. Након што скупи ауру елемента i, он може да повећа вредност вредност c за један.

Природно, Васа жели да максимизује ауру коју има након проласка кроз цео низ (приметите да ова вредност може да буде и негативна). Додатно, Васа жели да након проласка кроз низ вредност c буде тачно x.

Дат је низ p са n елемената. Исписати ауру коју Васа може да скупи за сваки подниз b дужине тачно k. Приметите да се ова скупљања одигравају независно.

Опис улаза

У првом реду су дата три цела броја n - дужина низа p, k - дужине поднизова на којима ће Васа скупљати ауру, и x - крајња вредност коефицијента c.

У другој линији стандардног улаза, дато је n целих бројева. i-ти од њих је p_i и представља вредност i-тог елемента низа p.

Опис излаза

У првој линији исписати n-k+1 бројева, који представљају максималну вредност ауре за сваки подниз дужине k низа p.

Пример 1

Улаз

5 3 2
1 -2 4 4 -5

Излаз

7 14 3

Објашњење примера 1

Постоје три подниза дужине тачно k = 3:

• [1, -2, 4] - Васа ће да повећа c са 1 на 2 након скупљања другог елемента низа, па је његова коначна аура 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] - Васа ће да повећа c са 1 на 2 након скупљања првог елемента низа, па је његова коначна аура 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] - Васа ће да повећа c са 1 на 2 након скупљања трећег елемента низа, па је његова коначна аура 1 \cdot b_1 + 1 \cdot b_2 + 1\cdot b_3 = 1 \cdot 4 + 1 \cdot 4 - 1 \cdot 5 = 3.

Пример 2

Улаз

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

Излаз

-12 -9 4 23

Ограничења

• 1 \leq x \leq k \leq n \leq 200.000.
• |p_i| \leq 10^9 за свако 1 \leq i \leq n.

Тест примери су подељени у 6 дисјунктних група:

• У тестовима вредним 10 поена: важи n \leq 20
• У тестовима вредним 10 поена: важи p_i \geq 0, за 1 \leq i \leq n.
• У тестовима вредним 15 поена: важи n \leq 300.
• У тестовима вредним 15 поена: важи n \leq 3.000.
• У тестовима вредним 20 поена: важи x = 2.
• У тестовима вредним 30 поена: без додатних ограничења.