Keď George R. R. Martin[^1] začal písať svoju ságu A Song of Ice and Fire[^2], túto otázku si kládol veľmi často. Veľmi rýchlo však dospel k presvedčeniu, že aj tak všetci musia zomrieť[^3] a jeho knihy sa stali krvavým festivalom. Ako skúsený autor však vie, že je dôležité, v akom poradí jednotlivé postavy zomrú.

Má Bran zomrieť skôr ako Arya? A čo s Theonom, poprípade Petyrom Baelishom? Prežije Daenerys svojich drakov, alebo ju Drogon spáli svojim plameňom a potom zomrie v boji proti Jaimimu Lannisterovi? Všetky tieto otázky si musel George položiť a rozmýšľať, ktorá odpoveď je najlepšia. Postupne sa dopracoval k jednej možnej permutácii úmrtí, ktorá sa mu zdala ako veľmi dobrá.

Stále si však nebol istý (predsa len, všetkých možných permutácií je faktoriál veľa) a preto skúšal túto permutáciu zmeniť. Postupne vyskúšal všetky jej cyklické rotácie a porovnával ich medzi sebou. K najlepšiemu zisteniu však prišiel, keď lexikograficky zoradil všetky tieto cyklické rotácie jednu pod druhú a pozrel sa na čísla v poslednom stĺpci. Zdalo sa mu, že toto poradie úmrtí bude najlepšie možné.

Skôr ako si ho však zapísal, do izby vnikol prievan a odfúkol mu všetky papieriky s permutáciami. Zúfalý George si ale pamätá niekoľko prvých čísel jeho vysnívanej permutácie a to, že táto permutácia bola lexikograficky najmenšia možná s takýmto začiatkom. Pomôžte mu zistiť, ako vyzerá jeho zvolená permutácia, lebo zabije vaše obľúbené postavy ako prvé[^4].

Úloha

Najskôr si opäť zopakujme ako vznikla Georgova žiadaná permutácia. Na začiatku má permutáciu $$P$$ zloženú z $$n$$ prvkov – čísel od $$1$$ po $$n$$. Postupne si zoberie všetky cyklické rotácie tejto permutácie. Cyklickú rotáciu permutácie dostanete tak, že odstránite niekoľko prvých členov $$P$$ a v takom istom poradí ich pridáte na koniec zvyšku tejto permutácie. Dostaneme teda $$n$$ cyklických permutácií, lebo aj pôvodná permutácia patrí medzi jej cyklické permutácie.

Tieto permutácie teraz lexikograficky usporiadame a v tomto poradí zoradíme pod seba. Permutácia je lexikograficky menšia ako iná permutácia, ak má na prvej pozícii zľava, kde sa tieto permutácie líšia, menšie číslo. Dostaneme tabuľku $$n\times n$$. Teraz si zoberme posledný stĺpec tejto tabuľky a dostaneme Georgovu vysnívanú permutáciu. Sami si rozmyslite, že táto postupnosť je naozaj permutácia.

Ukážme si tento postup na príklade. Majme permutácia $$P = (2, 4, 5, 1, 3)$$.

`cyklické rotácie       lexikograficky zoradené

2 4 5 1 3              1 3 2 4 5
4 5 1 3 2              2 4 5 1 3
5 1 3 2 4     ---->    3 2 4 5 1
1 3 2 4 5              4 5 1 3 2
3 2 4 5 1              5 1 3 2 4`

Výsledná permutácia je $$R = (5, 3, 1, 2, 4)$$.

A teraz prichádza vaša úloha. Poznáte niekoľko začiatočných prvkov permutácie $$R$$, ktorá vznikla z nejakej permutácie $$P$$ vyššie spomínaným postupom. Naviac viete, že $$R$$ je lexikograficky najmenšia permutácia, ktorá mohla vzniknúť takýmto spôsobom a má daný začiatok. Zistite, ako vyzerá permutácia $$R$$.

Formát vstupu

V prvom riadku je číslo $$n$$ udávajúce počet prvkov hľadanej permutácie. V druhom riadku je číslo $$m$$ – počet začiatočných prvkov permutácie $$R$$, ktoré poznáte.

Tretí riadok obsahuje $$m$$ čísel, ktoré určujú prvých $$m$$ prvkov permutácie $$R$$.

Formát výstupu

Vypíšte $$n$$ čísel, každé na samostatný riadok. Tieto čísla majú tvoriť permutáciu $$R$$, ktorá je lexikograficky najmenšia možná vzhľadom na podmienky vzniku a začiatočné prvky. V prípade, že takáto permutácia neexistuje, vypíšte reťazec Chybny vstup.

Hodnotenie

Vo všetkých vstupoch bude platiť, že $$n\leq 10^5$$ a $$m \leq \min(n,10^5)$$. Naviac môžete predpokladať, že v prvých dvoch testovacích sadách platí $$n\leq 10$$ a v ďalších dvoch sadách platí, že $$n \leq 100$$ a $$m \leq 50$$.

Príklady

Input:

5
2
2 4

Output:

2
4
1
5
3

Input:

5
1
1

Output:

Chybny vstup

Input:

10
3
3 8 6

Output:

3
8
6
1
2
5
4
9
10
7

1. Toto je len umelecké meno nášho obľúbeného Georga, vševedca, všeumelca a dobrodruha.↩

2. Z ktorej k dnešnému dátumu vyšlo už 5 kníh a bol k nej natočený úspešný seriál Game of Thrones.↩

3. Valar morghulis.↩

4. Samozrejme, zomrú aj tak, ale môžete im zabezpečiť trošku dlhší život, poprípade menej drastickú smrť.↩