bubblesort

Miruna a învăţat recent la ora de informatică algoritmul bubble sort. Mai jos puteţi vedea codul algoritmului în limbajul C++:

int steps = 0;
while (true) {
	++steps;
	bool isSorted = true;
	for (int i = 1; i < n; ++i)
		if (v[i] > v[i + 1]) {
			swap(v[i], v[i + 1]);
			isSorted = false;
		}
	if (isSorted) 
		break;
};

Miruna defineşte ordinul unei permutări ca fiind egal cu numărul de paşi necesari algoritmului pentru a sorta permutarea (adică valoarea variabilei steps în codul de mai sus la sfârşitul execuţiei).

Cerinţă

Dându-se trei numere naturale $N$, $M$ şi $K$ aflaţi care este cea de a $K$-a permutare în ordine lexicografică de lungime $N$ şi ordin $M$.

Date de intrare

Pe prima linie a fişierului de intrare bubblesort.in se vor afla trei numere naturale $N$, $M$ şi $K$, având semnificaţia de mai sus.

Date de ieșire

Pe prima linie a fişierului de ieşire bubblesort.out veţi afişa $N$ numere naturale despărţite prin spaţiu reprezentând permutarea cerută.

Restricții și precizări

• $1 \leq N \leq 300$
• $1 \leq M \leq N$
• Se garantează existenţa soluţiei pe datele de test.

Exemplul 1

bubblesort.in

7 4 123

bubblesort.out

1 5 3 6 2 4 7

Exemplul 2

bubblesort.in

20 5 1097525229548

bubblesort.out

2 7 1 3 4 6 5 10 13 11 9 8 15 12 19 17 16 14 20 18