M. Balance of Permutation
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

For a permutation $$$p$$$ of numbers from $$$1$$$ to $$$n$$$, its balance is defined as $$$\sum_{i = 1}^{n}{|p_i - i|}$$$. Your task is to find the $$$k$$$-th smallest lexicographically permutation of length $$$n$$$ with a balance equal to $$$b$$$.

Input

The standard input contains a single line with three integers $$$n$$$, $$$b$$$, and $$$k$$$ ($$$1 \leq n \leq 30; 0 \leq b; 1 \leq k$$$), as described in the problem statement.

It is guaranteed that there are at least $$$k$$$ permutations of length $$$n$$$ with a balance equal to $$$b$$$.

Note that the value of the parameter $$$k$$$ may not fit in a $$$64$$$-bit data type. In C++, we recommend using the __int128 type to store it.

Output

The output should contain $$$n$$$ integers in a single line – the sought permutation.

Examples
Input
6 6 6
Output
1 2 6 3 4 5
Input
30 300 3030303030303030303030
Output
1 2 3 4 9 23 20 28 24 16
21 17 27 29 8 26 25 30 19 18
22 12 7 13 6 10 5 15 14 11
Note

Consider the first sample test. There are $$$46$$$ permutations of length $$$6$$$ with a balance equal to $$$6$$$. Among them, the sixth smallest in lexicographic order is the permutation $$$[1, 2, 6, 3, 4, 5]$$$.

The line breaks in the second example were added to fit in the "output" section of the PDF statement. You do not need to add the line breaks in your actual output.