culegeri

Ultima atracție a lotului național de informatică este șahul. Așa că Gimi s-a decis să-și deschidă o afacere, aceea fiind să vândă culegeri de șah. Aceste culegeri conțin tactici nemaivăzute, deci cererea este ridicată.

În avans, el a primit lista de comenzi. Zilnic, timp de $N$ zile, el va trebui să livreze $c_i$ culegeri la finalul zilei $i$. Gimi și-a început afacerea prin cumpărarea unei fabrici ce poate produce $K$ culegeri pe zi, stocul inițial de culegeri fiind $S = 0$.

Zilnic, el poate alege una din următoarele două opțiuni:

• Gimi oprește producția în această zi și modernizează fabrica. În urma îmbunătățirilor, capacitatea de producție a fabricii va crește cu $1$ ($K \leftarrow K + 1$).
• Gimi urmărește cu atenție procesul de printare. Astfel, stocul de culegeri va crește cu $K$ ($S \leftarrow S + K$).

La finalul zilei $i$, el va livra $c_i$ culegeri ($S \leftarrow S - c_i$). Dacă nu are cel puțin $c_i$ culegeri în stoc, atunci lipsa lui de punctualitate va fi evidențiată, iar activitatea nu va mai putea continua.

Cerință

Cunoscând numărul de zile în care se desfășoară activitatea, producția zilnica inițială, respectiv lista cu cele $N$ comenzi, să se rezolve următoarele cerințe:

• Dacă $T = 1$, atunci Gimi vrea să afle numărul maxim de culegeri pe care le poate avea în stoc la finalul ultimei zile (a $N$-a zi).
• Dacă $T = 2$, atunci Gimi vrea să afle numărul maxim de culegeri pe care le poate avea în stoc la finalul celei de-a $i$-a zi, pentru fiecare $i$ de la $1$ la $N$.

Date de intrare

Prima linie din fișierul de intrare conține trei numere $T$, $N$ și $K$, separate prin câte un spațiu. A doua linie va conține $N$ numere, unde al $i$-lea număr reprezintă $c_i$, comanda de culegeri din a $i$-a zi.

Date de ieșire

• Dacă $T = 1$, atunci fișierul de ieșire va conține un singur număr natural, reprezentând numărul maxim posibil de culegeri rămase în stoc la finalul celei de a $N$-a zi.
• Dacă $T = 2$, atunci fișierul de ieșire va conține, pe o singură linie, $N$ numere naturale separate prin câte un spațiu, unde al $i$-lea număr reprezintă numărul maxim posibil de culegeri rămase în stoc la finalul celei de a $i$-a zi.

Restricții

• $1 \leq N \leq 500 \ 000$
• $0 \leq K \leq N$
• $0 \leq c_i \leq N \cdot K$
• Se garantează că există o modalitate prin care Gimi își va putea desfășura activitatea până în ultima zi inclusiv.
• Strategia utilizată pentru ziua $i$ nu trebuie neapărat să fie continuată în ziua $i + 1$. Se poate folosi o altă strategie, diferită de cea pentru ziua precedentă.

Exemple

culegeri.in

2 5 2
1 1 3 1 3

culegeri.out

1 2 1 2 2

culegeri.in

1 5 2
1 1 3 1 3

culegeri.out

2

Explicații

Pentru primul exemplu, $T = 2$, deci se rezolvă a doua cerință. Notăm cu "$P \ x$" zilele în care vom produce $x$ culegeri, iar cu "$I \ 1$" zilele în care vom crește producția cu 1. Strategiile optime, pentru fiecare zi, ar putea fi:

• ziua 1: $P \ 2$
• zilele 1-2: $P \ 2 \rightarrow P \ 2$
• zilele 1-3: $P \ 2 \rightarrow P \ 2 \rightarrow P \ 2$
• zilele 1-4: $P \ 2 \rightarrow I \ 1 \rightarrow P \ 3 \rightarrow P \ 3$
• zilele 1-5: $P \ 2 \rightarrow I \ 1 \rightarrow P \ 3 \rightarrow P \ 3 \rightarrow P \ 3$

Se observă că strategiile diferă în funcție de ziua în care se vor termina experimentele. Pentru zilele 1-4, capacitatea de producție va crește în a doua zi, dar pentru zilele 1-3, capacitatea de producție nu se va modifica.

În plus, este imposibilă creșterea capacității de producție în prima zi, deoarece stocul ar fi zero, iar Gimi trebuie să livreze o culegere.

Pentru al doilea exemplu, $T = 1$, deci se va rezolva prima cerință. Se va afișa doar stocul maxim posibil la finalul ultimei zile.