Combo Lock k-th Arrangement

HardCombinatoricsPermutation-RankFactorial-Number-SystemCounting6 hidden tests

A dial lock uses each of the numbers 1 through n exactly once in some order. Consider all n! orderings listed in lexicographic (dictionary) order and numbered starting from 1. Given n and an index k, output the k-th ordering in that list.

Input format

Line 1: an integer n. Line 2: an integer k (1-indexed, with 1 <= k <= n!).

Output format

One line: the k-th permutation of 1..n as n space-separated integers.

Constraints

1 <= n <= 8
1 <= k <= n!

Examples

Example 1

Input

3
4

Expected

2 3 1

Explanation

Order: 123,132,213,231,312,321. The 4th is 2 3 1.

Example 2

Input

4
1

Expected

1 2 3 4

Explanation

The 1st permutation is always the ascending order 1 2 3 4.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →