Počet bodov:
Program:  15b

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu loops_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Denisovi na denis@ksp.sk

Kika sa rozhodla, že napečie palacinky pre celú rodinu. Spravila teda cesto, zapla sporák a zohriala na ňom panvicu. Na neuveriteľne dlhý stôl naukladala neuveriteľne veľa tanierov, pekne vedľa seba ako sa na skúsenu gazdinú patrí, a začala piecť palacinky. Keď bola prvá palacinka upečená, Kika zavolala k svojmu neuveriteľne dlhému stolu celú rodinu a položila palacinku na prvý tanier na stole. Vždy, keď bola ďalšia palacinka hotová, Kika ju položila na prvý tanier na stole.

Keďže Kika dáva palacinky len na prvý tanier, jej rodina musela vymyslieť, ako sa rozdelia. Predsa len, je fajn byť prvý pri stole, ale čo ostatní? Jej rodina si teda vymyslela zaujímavé stravovacie návyky. Ak má niekto na svojom tanieri tri palacinky, tak jednu posunie doprava a ostatné dve zje. Nemôže predsa posunúť ďalej viac palaciniek ako by sám zjedol. Keď Kika dopečie poslednú palacinku, zaujíma ju, koľko palaciniek zostalo každému z rodiny na tanieri.

Úloha

Vašou úlohou je napísať program, ktorý vypíše koľko palaciniek zostalo každému z rodiny na tanieri po tom, ako Kika dopečie poslednú palacinku. Pri stole sa nachádza \(k\) členov rodiny a Kika upečie \(n\) palaciniek. Rodina sa správa podľa týchto stravovacích návykov:

  1. Kika vždy pokladá čerstvo upečenú palacinku na prvý tanier na stole.
  2. Ak má nejaký člen rodiny na tanieri 3 palacinky, tak dve zje a jednu posunie nasledujúcemu členovi rodiny. Kika, ako správna gazdiná, vie odhadnúť, koľko cesta prichystať. Preto posledný človek nikdy nebude musieť posúvať palacinku ďalej.
  3. Ak má akýkoľvek člen rodiny menej ako 3 palacinky, tak nerobí nič.

Formát vstupu

Na prvom riadku vstupu sú dve celé čísla \(n\) (\(1 \leq n \leq 10^{15}\)) a \(k\) (\(1 \leq k \leq 40\)). Číslo \(n\) reprezentuje počet palaciniek, ktoré Kika napečie, a \(k\) reprezentuje počet osôb pri stole.

Pri riešení v jazyku C++, Pascal, Java, a podobných, si dávajte pozor na maximálne číslo, ktoré sú schopné celočíselné premenné uložiť. Počet palacieniek môže v posledných troch sadách tieto limity prekročiť. Odporúčame použiť \(64\)-bitové premenné. V jazyku C++ preto namiesto typu int použite typ long long int.

Formát výstupu

Na výstup vypíšte riadok, na ktorom bude \(k\) čísiel, pričom \(k_i\) vyjadruje počet palaciniek, ktoré zostali človeku \(i\) na tanieri po tom, ako Kika dopiekla poslednú palacinku. Tieto čísla vypisujte na výstup bez medzier a za posledným číslom vypíšte znak konca riadku.

Hodnotenie

Vaše riešenie bude testované na 5 rôznych sadách vstupov. Rôzne sady sa budú líšiť špeciálnymi obmedzeniami:

Číslo sady 1 2 3 4 5
maximálne \(n\) \(100\) \(10\,000\) \(10^{12}\) \(10^{15}\) \(10^{15}\)
maximálne \(k\) \(10\) \(15\) \(30\) \(35\) \(40\)

Príklady

Input:

7 4

Output:

1200

Input:

12 5

Output:

01100

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.