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