Alex are pe un raft n jucării. Pe fiecare jucărie se află scris unul dintre numerele 1, 2, ..., n. Nu există două jucării pe care să fie scris acelaşi număr. După ce se joacă cu aceste jucării, Alex le pune din nou pe raft, aranjate în şir, astfel încât să existe cel puţin k dintre ele în ordine crescătoare (nu neapărat pe poziţii consecutive). Spre exemplu, pentru n=5 şi k=3 şirul de jucării 3 1 4 2 5 este corect, dar  4 3 5 2 1 nu este corect. Primul şir are jucării are cel puţin trei jucării aşezate în ordine crescătoare (de exemplu 1, 2, 5), iar cel de-al doilea nu are trei jucării în ordine crescătoare.

Cerinţă

Să se scrie un program care determină cea de a p-a modalitate de a aşeza jucăriile pe raft astfel încât să respecte condiţia din enunţ, considerând modalităţile în ordine lexicografică.

Date de intrare

Fişierul de intrare jucarii.in are pe prima linie numerele naturale n k p separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire jucarii.out va conţine o singură linie pe care vor fi scrise n numere naturale distincte cuprinse între 1 şi n, separate prin câte un singur spaţiu, reprezentând cea de a p–a modalitate în ordine lexicografică.

Restricţii

• 0 < k ≤ n < 11
• 0 < p ≤ maxim(numărul de modalităţi, 50050)
• Un şir de numere x=(x₁, x₂, ..., x_n) este mai mic în ordine lexicografică decât şirul y=(y₁, y₂, ..., y_n), dacă există un indice h, cu proprietăţile: x₁=y₁, …, x_h-1=y_h-1 şi x_h<y_h.

Exemple

jucarii.in	jucarii.out	Explicaţie
4 3 7	2 3 1 4	Modalităţile în ordine lexicografică sunt următoarele: 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 2 1 3 4 2 3 1 4 2 3 4 1 3 1 2 4 4 1 2 3

prof. Doru Popescu Anastasiu

C.N. "Radu Greceanu", Slatina

dopopan@yahoo.com