LEXI1 - Lexicographic Order 1
An ordering for the Cartesian product x of any two sets A and B with order relations <A and <B, respectively, such that if (a1, b1) and (a2, b2) both belong to AxB, then (a1, b1) < (a2, b2) iff either
- a1 < A a2, or
- a1 = a2 and b1 < B b2.
The lexicographic order can be readily extended to cartesian products of arbitrary length by recursively applying this definition, i.e., by observing that AxBxC = Ax(BxC).
When applied to permutations, lexicographic order is increasing numerical order. For example, the permutations of {1,2,3} in lexicographic order are 123, 132, 213, 231, 312, and 321.
You will be given a permutation of n first natural numbers. You need to find k-th lexicographically next permutation. Also we will consider that the lexicographically last permutation is followed by the first one in the ordering.
Input
The first line is number t - the amount of test cases. Each test case starts with numbers n and k. Then n natural numbers follow which are the elements of the given permutation.
Constraints
1 <= t <= 5
1 <= n <= 50000
0 <= k <= 100
Output
For each test case output the k-th lexicographically next permutation after the given one.
Example
Input: 3 3 3 1 2 3 3 2 2 1 3 3 8 2 3 1 Output: 2 3 1 3 1 2 3 2 1
Added by: | Spooky |
Date: | 2010-05-15 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |