Autonumbrid

문제

Marslased juurutavad uut autonumbrite süsteemi. Selles süsteemis on iga numbrimärk $NN$ arvu permutatsioon, see tähendab jada, milles arvud $1\dots N1\; \backslash ldots\; N$ esinevad igaüks täpselt ühe korra.

Administratiivselt jaguneb Marss lõuna- ja põhjapoolkeraks. Kuna on soovitav, et auto numbri järgi saaks tuvastada, kummalt poolkeralt see pärineb, otsustati, et lõunapoolkera saab $N!\mathrm{/}2N!/2$ leksikograafiliselt väiksemat ja põhjapoolkera $N!\mathrm{/}2N!/2$ leksikograafiliselt suuremat numbrit.

Poolkerade kubernerid tahtsid endale erilisi numbreid. Lõunapoolkera kuberner otsustas võtta endale oma poolkera numbritest leksikograafiliselt suurima ja põhjapoolkera kuberner oma poolkera numbritest leksikograafiliselt vähima.

Kirjuta programm, mis leiab, millised numbrid kubernerid endale saavad.

Meenutame, et $N!N!$ tähistab korrutist $1\cdot 2\cdot \dots \cdot N1\; \backslash cdot\; 2\; \backslash cdot\; \backslash ldots\; \backslash cdot\; N$ ning arvujada $a=(a_1,a_2,\dots ,a_n)a\; =\; (a\_1,\; a\_2,\; \backslash ldots,\; a\_n)$ on arvujadast $b=(b_1,b_2,\dots ,b_n)b\; =\; (b\_1,\; b\_2,\; \backslash ldots,\; b\_n)$ leksikograafiliselt väiksem, kui mingi indeksi $tt$ korral $a_1=b_{1}a\_1\; =\; b\_1$, $a_2=b_{2}a\_2\; =\; b\_2$, \ldots, $a_t=b_{t}a\_t\; =\; b\_t$, aga .

입력

Tekstifaili ainsal real on täisarv $NN$ ($2\le N\le 5\cdot {10}^{5}2\; \backslash le\; N\; \backslash le\; 5\; \backslash cdot\; 10^5$) --- Marsi autonumbrite pikkus.

출력

Tekstifaili väljastada täpselt kaks rida, kummalegi reale $NN$ tühikutega eraldatud täisarvu. Esimesele reale väljastada lõunapoolkera ja teisele põhjapoolkera kuberneri auto number.

2

1 2
2 1

3

2 1 3
2 3 1