Problem 1137. -- permutation

1137: permutation

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 72  Solved: 36
[Submit][Status][Web Board]

Description

大家知道,给出正整数n,则1到n这n个数可以构成n!种排列,把这些排列按照从小到大的顺序(字典顺序)列出,如n=3时,列出1 2 3,1 3 2,2 1 3,2 3 1,3 1 2,3 2 1六个排列。 
任务描述: 
给出某个排列,求出这个排列的下k个排列,如果遇到最后一个排列,则下1排列为第1个排列,即排列1 2 3…n。 
比如:n = 3,k=2 给出排列2 3 1,则它的下1个排列为3 1 2,下2个排列为3 2 1,因此答案为3 2 1。 

Input

第一行两个正整数n,k。第二行n个整数表示原始排列。

Output

一行n个整数表示所求排列。两个整数间用一个空格隔开,行尾无空格。

Sample Input

3 4
1 3 2

Sample Output

3 2 1

HINT

对于100%的数据,n<=20 给定输入保证是合法的1到n的排列,保证有解。

Source

[Submit][Status]