Vasa sakupljac aura

Vasa are 0 aure. Lui Vasa nu îi place acest lucru.

De aceea, a decis să adune aura parcurgând un șir. Formal, pentru un șir dat de numere întregi b de lungime k, Vasa pornește de la indicele i = 1 cu aura a = 0 și coeficientul c = 1. Apoi parcurge șirul și, pe rând, adună aura elementelor adăugând la aura sa valoarea c \cdot b_i. După ce adună aura elementului i, el poate mări valoarea coeficientului c cu unu.

În mod natural, Vasa dorește să maximizeze aura pe care o are după parcurgerea întregului șir (observați că această valoare poate fi și negativă). În plus, Vasa dorește ca, după parcurgerea șirului, valoarea lui c să fie exact x.

Este dat un șir cu p са n elemente. Afișați aura pe care Vasa o poate aduna pentru fiecare subșir b de lungime exact k. Observați că aceste adunări se desfășoară independent.

Descrierea intrării

În prima linie sunt date trei numere întregi:

n – lungimea șirului p, k - lungimea subşirurilor pe care Vasa le va parcurge pentru a aduna aura, și x - valoarea finală a coeficientului c.

În a doua linie a intrării standard, sunt date n numere întregi. Cel de-al i dintre ele este p_i și reprezintă valoarea celui de-al i element al șirului p.

​

Descrierea intrării

În prima linie se afișează n-k+1 numere, care reprezintă valoarea maximă a aurei pentru fiecare subșir de lungime k al șirului p.

Exemplul 1

Intrare

5 3 2

1 -2 4 4 -5

Ieșire

7 14 3

Explicația exemplului 1

Există trei subșiruri de lungime exact k = 3:

• [1, -2, 4] - Vasa va mări c de la 1 la 2 după ce adună al doilea element al șirului, așa că aura sa finală este 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 va mări c de la 1 la 2 după ce adună primul element al șirului, așa că aura sa finală este 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 va mări c de la 1 la 2 după ce adună al treilea element al șirului, așa că aura sa finală este 1 \cdot b_1 + 1 \cdot b_2 + 1\cdot b_3 = 1 \cdot 4 + 1 \cdot 4 - 1 \cdot 5 = 3.

Exemplul 2

Intrare

7 4 3

-10 2 2 -5 -4 5 7

Ieșire

-12 -9 4 23

Restricții

• 1 \leq x \leq k \leq n \leq 200.000.

• |p_i| \leq 10^9 pentru fiecare 1 \leq i \leq n.

Exemplele de test împărțite în 6 grupuri disjunctive:

• În testele care valorează 10 puncte: este valabil n \leq 20

• În testele care valorează 10 puncte: este valabil p_i \geq 0, pentru 1 \leq şi \leq n.

• În testele care valorează 15 puncte: este valabil n \leq 300.

• În testele care valorează 15 puncte: este valabil n \leq 3.000.

• În testele care valorează 20 puncte: este valabil x = 2.

• În testele care valorează 30 puncte: fără restricții suplimentare.