5. Korytnačie preteky

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabovi na [email protected]

Medzi matfyzákmi sú Korytnačie preteky veľmi obľúbenou spoločenskou hrou a to napriek tomu, že táto hra je primárne určená pre päťročné deti. Pri prvom opise je totiž naozaj veľmi jednoduchá. Hrací plán pozostáva z niekoľkých za sebou idúcich políčok a cieľom hráčov je dostať korytnačku ich farby čo najrýchlejšie do cieľa. Korytnačky sa však môžu hýbať iba pomocou kariet, ktoré hráči na striedačku vykladajú. Každá karta určuje farbu korytnačky a počet políčok, o ktoré sa má korytnačka posunúť (tento počet môže byť aj záporný, vtedy ide korytnačka dozadu).

Toto znie pomerne priamočiaro. Akurát, hráči poznajú iba farbu svojej korytnačky, nevedia za ktorú korytnačku hrajú súperi a na ruke môžu mať karty ľubovoľnej farby. Navyše, korytnačky majú vskutku špecifický spôsob pohybu. Ak je totiž korytnačka presunutá na políčko, na ktorom sú iné korytnačky, nepostaví sa vedľa nich, ale na ne. Všetky korytnačky stojace na tom istom políčku teda vždy tvoria jeden stĺpik. Novú korytnačku, prichádzajúcu na políčko, vždy položíme na vrch stĺpika. A keď sa niektorá z korytnačiek tvoriacich stĺpik pohne, zoberie so sebou (presnejšie, na sebe) všetky na nej stojace korytnačky.

Pri hre naozaj často vznikajú takéto stĺpiky korytnačiek, ktoré sa spoločne presúvajú. Hráči sa snažia takticky držať svoje korytnačky na vrchu týchto kôpok (aby im ich posúvali aj ostatní hráči), a potom vo vhodnej chvíli rýchlo utiecť do cieľa.

Jano a Žaba sú vášniví hráči. Vytvorili si dokonca viacero hracích plánov, v ktorých je čoraz viac políčok aj korytnačiek. Nedávno ich pri hraní prišiel navštíviť Syseľ, drgol však do stola a rozsypal im všetky korytnačky. Jano a Žaba by chceli túto partiu dohrať. Našťastie si pamätajú všetky karty, ktoré postupne zahrali. Teraz by potrebovali rýchlo zistiť, aké bolo rozloženie korytnačiek v momente, keď prišiel Syseľ. Pomôžete im?

Úloha

Dostanete popis hry, ktorá sa odohrávala na \(p\) políčkach s \(n\) korytnačkami. Políčka sú očíslované od 1 po \(p\), pričom políčko 1 je začiatok a políčko \(p\) je cieľ. Korytnačky sú očíslované od 1 po \(n\). Na začiatku všetky korytnačky tvoria jeden stĺpik na políčku 1. Poradie korytnačiek v štartovacom stĺpiku dostanete zadané.

Následne sa odohralo \(q\) kariet. Každá karta určuje korytnačku, ktorá sa pohla, a počet políčok, o ktoré sa posunula dopredu. Toto číslo môže byť kladné aj záporné.

Vašou úlohou je zistiť, ako vyzerá hrací plán po odohratí všetkých zadaných kariet.

Formát vstupu

V prvom riadku vstupu sú tri čísla \(n\), \(p\) a \(q\) – počet korytnačiek, počet políčok a počet zahraných kariet.

V druhom riadku je \(n\) medzerou oddelených čísel udávajúcich začiatočné postavenie korytnačiek na políčku 1. Prvé číslo určuje číslo korytnačky na samom spodku stĺpika, druhé je číslo korytnačky priamo nad ňou a tak ďalej až po posledné číslo označujúce najvyššie položenú korytnačku. (Všetky tieto čísla sú od 1 po \(n\) a sú navzájom rôzne.)

Nasleduje \(q\) riadkov popisujúce karty v poradí, v akom boli zahrané. Každý z týchto riadkov sa skladá z troch čísel \(k_i\), \(p_i\) a \(x_i\). Tento riadok udáva, že korytnačka \(k_i\) pri zahratí tejto karty stála na políčku \(p_i\) a posunula sa o \(x_i\) políčok dopredu. (Záporné \(x_i\) teda v skutočnosti označuje pohyb dozadu.)

Zadaný vstup je korektný. Môžete teda predpokladať, že korytnačky skončia po každom pohybe na niektorom z políčok \(1\) až \(p\) a korytnačka \(k_i\) pri zahratí \(i\)-tej karty naozaj stojí na políčku \(p_i\).

Formát výstupu

Na výstup vypíšte \(p\) riadkov. V \(i\)-tom z týchto riadkov vypíšte popis korytnačiek na \(i\)-tom políčku. Prvé číslo riadku (označme ho \(x_i\)) udáva počet korytnačiek na tomto políčku. Zvyšok riadku má tvoriť ďalších \(x_i\) čísel: čísla korytnačiek na tomto políčku v poradí od spodku stĺpika po jeho vrch.

Hodnotenie

Váš program bude otestovaný na piatich vstupoch. Hodnoty \(n\), \(p\) a \(q\) v týchto vstupoch sú uvedené v tabuľke. Navyše, vo treťom vstupe platí, že každý presun korytnačky smeruje na prázdne políčko. V tomto vstupe sa teda nestane, že by sa korytnačka postavila na chrbát inej (stále však môžu cestovať v kôpke určenej z počiatočného rozostavenia).

Príklad

Input:

5 7 4
2 4 1 3 5
1 1 3
3 4 -3
4 1 5
1 4 2

Output:

1 2
0
0
0
0
4 4 3 5 1
0

Máme päť korytnačiek, sedem políčok a štyri zahrané karty. Na začiatku sú na políčku 1 korytnačky v poradí 2, 4, 1, 3, 5 zdola hore.

Potom sa postupne udeje nasledovné:

• Korytnačka 1 sa z políčka 1 pohne o 3 dopredu, na políčko 4. Na chrbte so sebou odnesie aj korytnačky 3 a 5.

• Korytnačka 3 sa z políčka 4 pohne o \(-3\) dopredu, teda naspäť na políčko 1. Na chrbte so sebou odnesie aj korytnačku 5. Na políčku 1 je teraz stĺpik 2, 4, 3, 5, zatiaľ čo na políčku 4 je samotná korytnačka 1.

• Korytnačka 4 sa z políčka 1 pohne o 5 dopredu. Na políčku 1 zostane len korytnačka 2, ostatné korytnačky odnesie korytnačka 4 so sebou na políčko 6.

• Korytnačka 1 sa zo svojho aktuálneho políčka 4 pohne o 2 dopredu a tam naskočí na vrch stĺpika.