Given an integer n and a permutation of numbers 1, 2 ... , n-1, n write a program to print the permutation that lexicographically precedes the given input permutation. If the given permutation is the lexicographically least permutation, then print the input permutation itself.

Input Format:

First line is the test cases and second line contains value of integer n: 1 ≤ n ≤ 1,000,000
third line is a space separated list of integers 1 2 ... n permuted in some random order

Output Format:

Output a single line containing a space separated list of integers which is the lexicographically preceding permutation of the input permutation.

SAMPLE INPUT
1
3
1 3 2

SAMPLE OUTPUT
1 2 3

见题面

见题面