Počet bodov:
Popis:  9b
Program:  6b

Kde bolo tam bolo, za bielym oblúkovým mostom a za dvoma veľkými semafórovými križovatkami, bola raz jedna škola. V tejto škole bola jedna trieda, a jej triedny učiteľ Ondrej si ju veľmi pochvaľoval. Jej žiaci totiž chodili na informatické sútaže. Vyhrali na nich kopu trofejí, každú žiarivejšiu ako prechádzajúcu.

Jedného dňa si Ondrej povedal, že tak krásnych trofejí je v jeho kabinete škoda. Aby jeho žiaci mohli vidieť plody svojej práce, rozhodol sa, že ich vyloží na poličku v triede. Polička je však na všetky trofeje priúzka, Ondrej preto vystavil len tie najžiarivejšie.

Prišla jar, a spolu s ňou začalo do triedy prenikať čím ďalej tým viac slnečných lúčov. Polička s trofejami sa každé ráno trblietala prekrásnymi farbami. Ondrej si však po chvíli začal všímať aj jej temnú stránku. Trofeje žiarili tak výrazne, až to začalo všetkých v miestnosti oslepovať.

S tým treba niečo robiť! Ondrej teda vytiahol krabicu so zvyškom trofejí a začal dumať. Vie, ako najviac môže polička žiariť aby žiakov ešte neoslepovala. Zároveň ju však nechce mať ani o kúsok matnejšiu, žiaci si predsa zaslúžia vidieť tie najžiarivejšie trofeje.

Ondrej má na výber \(n\) trofejí. Jeho žiaci vyhrávali čím ďalej tým žiarivejšie trofeje a tak \(i\)-ta trofej má žiarivosť \(i\). Na poličku sa zmestí \(k\) trofejí, jej žiarivosť je súčtom žiarivostí jednotlivých trofejí. Najväčšia žiarivosť poličky, akú si môže Ondrej dovoliť, je \(s\). Pomôžete mu vybrať tie správne trofeje?

Úloha

Spomedzi čísel \(1, 2, ..., n\) vyberte \(k\) takých, že ich súčet je presne \(s\).

Formát vstupu

Na vstupe dostanete tri celé čísla \(n\), \(k\), \(s\) oddelené medzerami. \(1 \leq n\leq 1\,000\,000\) – počet trofejí, \(1 \leq k \leq n\) – šírka poličky, \(1 \leq s \leq 2^{40}\) – ideálna žiarivosť poličky.

Na prácu s veľkými číslami1 použite typ long long v C++ a Int64 v Pascale.

Formát výstupu

Na jediný riadok výstupu vypíšte \(k\) medzerou oddelených čísel – čísla (žiarivosti) trofejí, ktoré má Ondrej vyložiť na poličku. Na poradí vypísaných čísel nezáleží.

Ak dobrých výberov trofejí existuje viac, vypíšte ľubovoľný z nich. Ak žiadny dobrý výber trofejí neexistuje, vypíšte \(-1\).

Príklad

Input:

6 3 11

Output:

1 4 6

Rovnako dobrý výber trofejí je napríklad aj \(6\), \(2\), \(3\).

Input:

5 2 10

Output:

-1

Dve najžiarivejšie trofeje, ktoré môže Ondrej vystaviť sú \(4\) a \(5\), ani tie však nie sú dosť oslnivé.


  1. 64-bitové čísla s rozsahom \(-2^{63}\)\(2^{63}-1\)

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.