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 поени: без додатних огранїченьох.