Elevi Pentru Elevi Arges - X | Bile14

Ionuț tocmai a împlinit 14 ani și a primit cadou de ziua lui un set de $N$ bile de biliard numerotate de la $1$ la $N$ și un aparat de fotografiat. Bilele sunt așezate într-o ordine oarecare.

Fiind pasionat de matematică, el își imaginează un joc alcătuit din $K$ pași. El vrea ca, la finalul jocului, bilele să fie așezate într-o anumită ordine cerută de fratele său, conform regulilor jocului:

• La primul pas, Ionuț așază bilele de biliard pe masă într-o ordine oarecare și fotografiază așezarea acestora. El va avea nevoie de fotografia facută pe toată durata jocului.
• Apoi, parcurge cei $K - 1$ pași rămași. La fiecare pas, toate bilele sunt repoziționate. Astfel, pentru a determina ce bilă trebuie pusă pe o anumită poziție $i$, cu $1 \le i \le N$, Ionuț caută în fotografie ce bilă se afla pe poziția $i$, la începutul jocului. Fie $Q$ numărul de pe acea bilă. Ionuț va pune acum pe poziția $i$ bila ce, la pasul anterior, se afla pe poziția $Q$.

Cerință

Ionuț își propune să afle care sunt toate modalitățile posibile de așezare inițială a bilelor astfel încât, în urma parcurgerii pașilor jocului, bilele să fie așezate în ordinea dorită de fratele său.

Date de intrare

Pe prima linie a fișierului de intrare bile14.in se vor afla două numere naturale în această ordine:

• $N$ - numărul de bile pe care le are Ionuț;
• $K$ - numărul de pași pe care îi va avea jocul.

Pe cea a doua linie a fișierului se vor găsi $N$ numere naturale separate prin câte un spațiu, reprezentând ordinea bilelor cerută de fratele lui Ionuț.

Date de ieșire

Fișierul de ieșire bile14.out va conține mai multe șiruri, fiecare pe câte o linie, afișate în ordine lexicografică.
Fiecare șir va fi alcătuit din $N$ numere naturale separate prin câte un spațiu.
Fiecare dintre aceste șiruri reprezintă o posibilă așezare inițială a bilelor care, în urma parcurgerii pașilor jocului, va conduce la ordinea dorită de fratele lui Ionuț.

Restricții și precizări

• $N \le 9$
• $2 \le K \le 10^9$
• Va exista întotdeauna cel puțin o modalitate de așezare a bilelor ce va conduce la ordinea dorită.
• Se oferă 10 puncte din oficiu.

Exemplu

bile14.in

5 3
1 2 3 5 4

bile14.out

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

Explicație

Cele trei șiruri obținute reprezintă toate modalitățile posibile de a așeza inițial bilele astfel încât, în urma jocului, să se ajungă la șirul dat de fratele lui Ionuț.

Pentru primele două soluții din exemplul de mai sus, jocul se desfășoară astfel:

Se observă că, pentru cele două soluții explicate, s-a afișat șirul determinat de numerele bilelor pe linia numită Așezarea inițială (După Pasul 1) și s-a ajuns, pe ultima linie, la șirul inițial, aflat în fișierul de intrare.