LEXI3 - Lexicographic Order 3

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 permutaion. Also we will consider that the lexicographically last permutaion 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 <= 100
1 <= n <= 250
0 <= k < n!

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

hide comments
2010-11-08 09:04:21 Spooky
the first will be
1 2 3 4 5 6 7 8 9 10
2010-10-05 14:19:24 aditya kumar
if n=10
then its 1st permutation will be
1 2 3 4 5 6 7 8 9 10
or
10 1 2 3 4 5 6 7 8 9
???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.