7. Och, koho len mám zabiť?

Keď George R. R. Martin¹ začal písať svoju ságu A Song of Ice and Fire², 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ť³ 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é⁴.

Ú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