In MathemIsland, the wildlife is very diverse. There are roots, trees, leaves, pigeons – everything you'd find in a math book. And everywhere you look, there is a permutation.
ICPC University has devised a systematic way to catalog these permutations. Specifically, because inversions are of utmost importance in studying wildlife genetics, ICPC University has decided to sort all $$$N!$$$ permutations of the integers from $$$1$$$ to $$$N$$$: first by the number of inversions and, in the case of a tie, by lexicographic order. This approach uniquely identifies each permutation by an integer from $$$1$$$ to $$$N!$$$, indicating its position in the sorted list of all $$$N!$$$ permutations.
Thus, the identity permutation ($$${1}, {2}, \ldots, {N}$$$), which is the only permutation with zero inversions, is assigned the identifier $$$1$$$, while the reverse identity permutation ($$${N}, {N-1}, \ldots, {1}$$$), which is the only one with the maximum number of inversions, is assigned the identifier $$$N!$$$.
As part of the team implementing the ICPC University database, your task is to retrieve a specific permutation based on its identifier. Write a program that, given two integers $$$N$$$ and $$$K$$$, outputs the permutation of the integers from $$$1$$$ to $$$N$$$ corresponding to identifier $$$K$$$.
Remember that the number of inversions in a permutation is the number of pairs of elements that are out of their natural order. That is, for a permutation $$$\pi$$$ with $$$N$$$ elements, its number of inversions $$$\mathop{\mathrm{inv}}(\pi)$$$ is defined as $$$$$$\mathop{\mathrm{inv}}(\pi) = \left| \{ (i, j) : 1 \leq i \lt j \leq N \land \pi(i) \gt \pi(j) \} \right| \enspace$$$$$$
The input consists of a single line that contains two integers $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) and $$$K$$$ ($$$1 \leq K \leq \min(N!, 4 \cdot 10^{18})$$$).
Output a single line with $$$N$$$ integers, describing the $$$K$$$-th permutation of the integers from $$$1$$$ to $$$N$$$, considering permutations sorted according to the university's criteria.
4 10
1 4 3 2
5 120
5 4 3 2 1
16 12345678901234
2 13 8 10 3 15 16 5 11 12 1 9 7 6 14 4
| Name |
|---|


