Smallest Permutation with One Swap

Given an integer array A of length N, you are allowed to swap at most one pair of elements. Your task is to determine the lexicographically smallest permutation that can be obtained by performing at most one swap.

For two arrays \(X\) and \(Y\) of equal length, we say \(X\) is lexicographically smaller than \(Y\) if there exists an index \(k\) (\(1 \le k \le N\)) such that \(X_i = Y_i\) for all \(i < k\) and \(X_k < Y_k\). In other words, you need to find a permutation \(P\) among all possible arrays obtainable by swapping at most one pair of indices, such that \(P\) is the smallest in lexicographical order.

You will be given T test cases. For each test case, the first input line contains an integer N representing the number of elements, and the next line contains N space-separated integers, the elements of the array A.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
N1
A1 A2 ... AN1
N2
A1 A2 ... AN2
...
NT
A1 A2 ... ANT

Where:

• T: The number of test cases.
• For each test case, the first line contains an integer N (the size of the array), followed by a line containing N space-separated integers.

outputFormat

For each test case, output a single line on standard output (stdout) representing the lexicographically smallest permutation after performing at most one swap. The elements in the permutation should be separated by a space.

## sample

2
4
4 3 2 1
5
5 4 3 2 1

1 3 2 4
1 4 3 2 5

</p>