Vytvořte program, který setřídí zadané záznamy podle číselného klíče.

Vstup

Na první řádce je číslo N oznamující počet záznamů. Druhá řádka obsahuje schéma. Schéma je výčet jmen položek, které obsahuje každý záznám. Jednotlivá jména jsou oddělena stejně jako záznamy ;(středníkem).

Jedno ze jmen obsahuje za jménem * (hvězdičku). Tím se označuje klíč, podle kterého budou všechny záznamy setříděny na výstupu. Klíč je typu číslo (integer).

[N]
<položka1-jméno>;<položka2-jméno>;...;<položkaI-jméno>*;...;<položkaM-jméno>
<záznam1-položka1>;...;<záznam1-položkaM>
...
<záznamN-položka1>;...;<záznamN-položkaM>

Výstup

Výstup má podobný formát jako vstup. Na první řádce již není počet záznamů, ale rovnou schéma. Následuje opět výčet N setříděných záznamů (od nejmenšího po největší). Položka, která byla použita jako klíč, se vypíše první, pořadí ostatních položek se nemění.

<položkaI-jméno>*;<položka1-jméno>;<položka2-jméno>;...;...;<položkaM-jméno>
<záznam1-položkaI>;<záznam1-položka1>;...;<záznam1-položkaM>
...
<záznamN-položkaI>;<záznamN-položka1>;...;<záznamN-položkaM>

Poznámky

• Je možné používat libovolné nesetříděné kontejnery (pole, List, ...).

• Třídění si musíte naprogramovat sami.

  • Nemusíte vymýšlet nic komplikovaného, libovlný stabilní třídící algoritmus s kvadratickou časovou složitostí na splnění úlohy stačí.

  • Nezapomeňte převést hodnoty, podle kterých třídíte, na čísla, při jejich porovnání jako stringů byste dostali špatné výsledky.

• Pokud má více záznamů stejný klíč, zachovává se na výstupu pořadí ze vstupu.

• Za posledním (jménem) záznamem není středník

• Jména i jednotivé položky mohou obsahovat mezery.

• Není potřeba validovat vstupy.

• Klíč je označován i ve výstupním souboru hvězdičkou.

Příklad vstupu

6
jmeno;vek*
adam;1
blazej;5
franta;5
cecilie;10
dana;2
eva;3

Příklad výstupu

vek*;jmeno
1;adam
2;dana
3;eva
5;blazej
5;franta
10;cecilie