A1 - Šuflík

Na povale starého rodinného domu sme našli tajomný šuflík. Keď sme ho otvorili, zbadali sme, že je v ňom päť puntíkov piatich druhov: jeden cuplík, jeden poklík, jeden tuplík, jeden pevtík a jeden todlík. Ich životný štýl je pomerne zložitý, preto čítajte pozorne.

Každý z týchto druhov puntíkov je sčasti chlpatý a sčasti plešatý. Mieru týchto vlastností nazveme chlpatosť a plešatosť. Každý druh obdivuje jeden druh a nenávidí nejaký iný druh puntíkov:

• Cuplíky obdivujú poklíky a nenávidia tuplíky.
• Poklíky veľmi obdivujú cuplíky, ale nenávidia pevtíky.
• Tuplíky obdivujú samé seba a nenávidia todlíky.
• Pevtíky naopak obdivujú todlíky, no nenávidia cuplíky.
• Poklíky sú obdivované aj todlíkami, ktoré nenávidia pevtíky.

Akonáhle sme šuflík otvorili, dostal sa dovnútra kyslík a puntíky sa začali rýchlo miesiť. Všetky puntíky sa miesia súčasne, pričom jedno zamiesenie trvá jednu sekundu. Ak bol šuflík otvorený T sekúnd, stihli sa puntíky T-krát zamiesiť.

V prvej fáze zamiesenia sa zmenia počty puntíkov tak, že počet puntíkov nejakého druhu po tejto fáze bude chlpatosť druhu * počet nimi obdivovaných puntíkov pred zamiesením - plešatosť druhu * počet nimi nenávidených puntíkov pred zamiesením. V druhej fáze zamiesenia sa v šuflíku zjavia štyri nové cuplíky, dva poklíky, sedem pevtíkov, no zmizne jeden tuplík a tri todlíky.

V živote puntíkov sú dôležité len čísla v rozsahu od 0 po M-1, preto počty členov jednotlivých druhov vyjadrujeme ako zvyšok po delení M. Akonáhle by mal počet jedincov nejakého druhu klesnúť pod 0, zjaví sa nových M jedincov.

Úloha

Vstup

Výstup

A1

1 ≤ T,M ≤ 10⁶

A2

1 ≤ T ≤ 10¹⁸

1 ≤ M ≤ 10⁹+47

Príklad 1

Vstup:

3 100000
1 1
2 1
3 1
4 1
5 1

Výstup:

3 7 0 9 99990

Príklad 2

Vstup:

1234 1000
1 0
1 0
7 6
6 7
0 1

Výstup:

703 703 899 922 447