Zadanie

Farma na baktérie

Počet bodov: 35, časový limit: 300ms

Byť farmárom je hračka, však?

Zo zeme vám rastie jedlo. Ak ho dáte sliepke, zjaví sa vám vajce a aj tej sliepky bude o kúsok viac. Kiežby. O zvieratá sa treba starať. Rastliny treba polievať. Treba dávať pozor na škodcov. Pre Romana, ktorému minulý rok vyschol kaktus, to zjavne kariéra nebude.

Ale Roman je vynaliezavý a našiel si stvorenie, pre ktoré je ako stvorený: baktérie!

Stačí si kúpiť akvárko, dať doňho nejaké baktérie, chvíľu ho neumývať a baktérie si žijú ako v raji.

Roman si zvolil špeciálnu pestovateľskú odrodu baktérie Xellosus Luxus Kaaespeenzis, ktorá sa každý deň rozmnoží na \(k\) kópií. Samozrejme, na ďalší deň sa každá z nich opäť rozmnoží na \(k\) kópií, a tak ďalej.

Dostal už aj prvú objednávku: za \(n\) dní musí vypestovať presne \(m\) baktérií, na použitie v tajných výskumných prácach Prírodovedeckej fakulty Univerzity Komenského.

Aby však príliš nedokaličil udomácnené akváriové baktérie, nemôže do akvária Roman pridať viac ako \(k-1\) nových baktérií denne.

Romana baví pestovanie baktérií, nie matematika. Pomôžte mu vypočítať, koľko baktérií má pridať v každom z \(n\) dní, aby mal nakoniec \(m\) vypestovaných baktérií.

Vstup a výstup

Formálne, pestovanie baktérií funguje nasledovne:

1. Cez noc sa každý jedinec Xellosus Luxus Kaaespeenzis, už prítomný v akvárku, rozdelí na \(k\) jedincov.
2. Ráno sa Roman rozhodne, koľko nových jedincov, medzi \(0\) a \(k-1\), vložiť do akvárka.

Keď Roman (ne)vloží baktérie do akvárka v \(n\)-té ráno, akvárko pošle PriFUKu, kam dorazí na obed, ešte pred rozmnožením baktérií. Musí sa v ňom nachádzať práve \(m\) jedincov Xellosus Luxus Kaaespeenzis.

V prvom riadku sú tri celé čísla \(n\), \(m\), \(k\) – počet dní ktoré Roman má na vybavenie objednávky, počet baktérií, ktoré musí vypestovať a koeficient množenia baktérií.

Platí \(1 \leq n \leq 10^3\), \(1 \leq m \leq 10^{18}\) a \(1 \leq k \leq 10^9\). Navyše, v polovici vstupov \(k = 2\).

Dávajte si pozor na veľkosť premenných. Naozaj.

Ak Roman nestíha vypestovať presne \(m\) baktérií za \(n\) dní postupom popísaným vyššie, vypíšte do jedného riadku číslo \(-1\).

V opačnom prípade vypíšte \(n\) medzerou oddelených celých čísel z rozmedzia \([0,k-1]\): počet baktérií, ktoré má Roman pridať do farmy v prvý deň, v druhý ďen, …, v \(n\)-tý deň.

Za posledným číslom vypíšte znak konca riadku, nie medzeru.

Príklad

Input:

3 5 2

Output:

1 0 1

V prvý deň vložíme jednu baktériu. Tá sa na druhý deň rozmnoží na dve, ktoré sa v tretí deň rozmnožia na štyri. Roman pridá poslednú, piatu baktériu, a veselo pošle zásielku.

Input:

3 1000 2

Output:

-1

Za tri dni takúto veľkú populáciu Roman vypestovať nestihne.