Fixed Point Permutations

Time limit1sMemory limit512 MB

Summary

Find the kth lexicographically smallest permutation of 1..n having exactly m fixed points, or print -1 if fewer than k exist.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Greedy, Math
Solved: No attempts yet

Problem

A permutation of size n is a list of integers (p1, p2, ..., pn) from 1 to n such that each number appears exactly once.

The number of fixed points of a permutation is the number of indices i such that pi = i.

Given three numbers n, m, and k, find the kth lexicographically smallest permutation of size n that has exactly m fixed points. If there are fewer than k permutations that satisfy the condition, print -1.

Input

The single line of input contains three space-separated integers

n (1 ≤ n ≤ 50) m (0 ≤ m ≤ n) k (1 ≤ k ≤ 1018)

where n is the size of the permutations, m is the number of desired fixed points, and the output should be the kth lexicographically smallest permutation of the numbers 1 to n that has exactly m fixed points.

Output

Output the desired permutation on a single line as a sequence of n space-separated integers, or output -1 if no such permutation exists.

Examples3

Example 1
Input
```
3 1 1
```
Expected output
```
1 3 2
```
Example 2
Input
```
3 2 1
```
Expected output
```
-1
```
Example 3
Input
```
5 3 7
```
Expected output
```
2 1 3 4 5
```