Permutation Problem

Interview

Time limit2sMemory limit1024 MB

Summary

Given n and k, find the k-th permutation of 1 to n in lexicographic order in which the numbers 1 and 2 are not adjacent.

Level: Medium5 of 10
Topics: Combinatorics, Backtracking
Solved: No attempts yet

Statement

A permutation of the numbers from 1 to $n$ is a sequence $p_1, \ldots, p_n$ in which each of these numbers appears exactly once.

Permutation $P=p_1 p_2 \ldots p_n$ comes before permutation $Q = q_1 q_2 \ldots q_n$ in lexicographic order if, for some $k$ , $p_t = q_t$ for all $1 \le t \le k$ and $p_{k+1} < q_{k+1}$ .

Consider all permutations of the numbers from 1 to $n$ in which the numbers $1$ and $2$ are not in adjacent positions. Sort them in lexicographic order. Find the permutation that is $k$ -th in this order.

Input

The first line contains two positive integers $n$ and $k$ ( $1 \le n \le 9$ , $1 \le k \le n!$ ). It is guaranteed that the permutation with this number exists.

Output

Print the answer to the problem.

Examples2

Example 1
Input
```
3 1
```
Expected output
```
1 3 2
```
Example 2
Input
```
4 6
```
Expected output
```
2 3 4 1
```