Depas
UŽDUOTIS
Viena Suomijos technologijos firma turi didelį stačiakampį depą. Depe dirba darbininkas ir vadybininkas. Stačiakampis depas padalintas į lygius kvadratus, t.y. jis turi eilutes (eiles) ir stulpelius. Eilės sunumeruotos pradedant nuo viršaus skaičiais 1, 2, ..., stulpeliai – pradedant iš kairės skaičiais 1, 2 ....

Depe saugomi konteineriai. Kiekvienas konteineris turi skirtingą identifikacijos numerį ir užima lygiai vieną kvadratą. Depas yra toks didelis, kad bendras atsiųstų konteinerių skaičius visada yra mažesnis negu eilučių skaičius ir mažesnis negu stulpelių skaičius. Konteineriai niekada neišgabenami iš depo, tačiau laikas nuo laiko ten atsiunčiamas naujas konteineris. Į depą konteineriai patenka pro viršutinį kairįjį kampą.

Darbininkas tvarko konteinerius taip, kad juos galėtų nesunkiai rasti. Jis konteinerius krauna į depą pradėdamas nuo viršutinio kairiojo kampo ir tai daro tokiu būdu:

Laikykime, kad naujai atvežto konteinerio numeris yra k (trumpiau, konteineris k). Darbininkas eina pirmąja eile iš kairės į dešinę ir ieško pirmo konteinerio, kurio identifikacijos numeris būtų didesnis už k. Jei tokio konteinerio neranda, tuomet padeda konteinerį k pirmoje eilėje kairiausiame laisvame kvadrate (t.y. konteinerių eilės gale arba pirmame eilės kvadrate, jeigu ši eilė tuščia). 

Jeigu toks konteineris l randamas, tuomet l pakeičiamas konteineriu k, o konteineris l dedamas tolesnę eilę (jos numeris vienetu didesnis nei prieš buvusios), naudojantis tuo pačiu metodu ir t.t. Jei pasiekiama tuščia eilė, konteineris dedamas pirmame (kairiausiame) tos eilės kvadrate.

Darbininkas tęsia darbą tol, kol padeda konteinerį tuščioje vietoje. 

Jei į depą konteineriai buvo atsiųsti šitokia tvarka: 3,4,9,2,5,1 tai darbininkas juos išdėstė taip: 
1 4 5
2 9
3

Tuo metu pasirodė vadybininkas ir įvyko toks pokalbis:
Vadybininkas: Ar konteineris 5 buvo gautas anksčiau nei konteineris 4?
Darbininkas: Ne, tai neįmanoma.
Vadybininkas: Aha, jūs galite nustatyti konteinerių gavimo tvarką pagal jų išdėstymą.
Darbininkas: Bendru atveju, ne. Pavyzdžiui, šiuo atveju konteineriai į depą galėjo būti atsiųsti ir tokia tvarka:3,2,1,4,9,5, arba tokia: 3,2,1,9,4,5, arba dar kitu iš likusių 14 galimų būdų.

Kadangi vadybininkas nenorėjo pasirodyti nesuprantąs, jis toliau nebesiaiškino. Jūs turite pagelbėti vadybininkui: parašykite programą, kuri pagal duotą konteinerių išdėstymą suskaičiuotų visus galimus jų atsiuntimo būdus.

PRADINIAI DUOMENYS IR REZULTATAI
Pradiniai duomenys įrašyti byloje depot.in. Pirmoje eilutėje įrašytas vienas sveikasis skaičius R: eilučių, kuriose yra konteinerių, skaičius. 

Likusiose R eilučių įrašyti duomenys apie 1,...R eilutes. Pirmas skaičius eilutėje yra sveikasis skaičius M: konteinerių skaičius toje eilutėje. Toliau eilutėje įrašyta M skaičių: konteinerių identifikatoriai. 

RIBOJIMAI
Konteinerių identifikatoriams I galioja nelygybė 1I50. Depe gali būti ne daugiau N konteinerių (1N13).

REZULTATAI
Rezultatų bylos vardas yra depot.out. Joje turi būti tiek eilučių, kiek yra galimų konteinerių atsiuntimo būdų. Kiekvienoje tų eilučių turi būti N skaičių: konteinerių numeriai jų atvykimo tvarka. Reikia pateikti tik skirtingus variantus. 

PRADINIŲ DUOMENŲ IR REZULTATŲ PAVYZDŽIAI

1 pavyzdys: depot.in				depot.out

3 2 1 4 9 5 
3 2 1 9 4 5 
3 4 2 1 9 5 
3 2 4 1 9 5 
3 2 9 1 4 5 
3 9 2 1 4 5 
3 4 2 9 1 5 
3 4 9 2 1 5 
3 2 4 9 1 5 
3 2 9 4 1 5 
3 9 2 4 1 5 
3 4 2 9 5 1 
3 4 9 2 5 1 
3 2 4 9 5 1 
3 2 9 4 5 1 
3 9 2 4 5 1

3
3 1 4 5
2 2 9
1 3

2 pavyzdys: 	depot.in				depot.out

3 1 2
1 3 2

2
2 1 2
1 3

VERTINIMAS
Jei rezultatų byla bus tuščia arba joje bus neteisingų atsakymų, testas bus įvertintas 0 balų. Jei rezultatų byloje bus išvardinti visi variantai ir tik po vieną kartą, už testą bus skiriami 4 balai. Jei byloje bus bent pusė variantų ir visi variantai bus pakartoti tik po vieną kartą, už testą bus skiriami 2 balai. Jei byloje bus mažiau nei pusė variantų ir/arba kai kurie jų bus pakartoti kelis kartus, už testą bus skiriama 25 balai.