Permutation Order

Interview

Time limit2sMemory limit128 MB

Summary

Given N, either compute the k-th lexicographic permutation of 1..N or find the rank of a given permutation, using factorial number system logic.

Level: Medium4 of 10
Topics: Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

There are N! permutations made by using each integer from 1 through N exactly once.

Permutations are ordered lexicographically. Compare two permutations from left to right; at the first position where they differ, the permutation with the smaller number comes earlier. For N=3, the order is {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}.

Given N, perform one of two tasks. Task 1 asks for the k-th permutation. Task 2 asks for the 1-based position of a given permutation.

Input

The first line contains an integer N (1 <= N <= 20).

The first integer on the second line is the task number. If it is 1, it is followed by an integer k (1 <= k <= N!). If it is 2, it is followed by N integers forming a permutation of 1 through N.

Output

For task 1, output the N integers of the k-th permutation separated by spaces. For task 2, output the 1-based lexicographic position of the given permutation.

Examples2

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