Rearrange Array with Limited Adjacent Differences

You are given an array of integers. Your task is to rearrange the array so that the absolute difference between any two consecutive elements is at most 1, i.e., ( |a_{i+1} - a_i| \le 1 ) for all valid indices. If such a rearrangement is possible, output any one valid ordering of the array. Otherwise, output -1.

The problem requires you to check the possibility of rearranging the array and then output the rearranged order if it exists. Notice that sorting the array is a natural candidate because if the numbers can be arranged to satisfy the condition, the sorted order will always work. However, if any adjacent difference in the sorted order exceeds 1, the rearrangement is impossible.

inputFormat

The input is read from standard input (stdin). The first integer ( T ) indicates the number of test cases. Each test case starts with an integer ( n ) (the size of the array), followed by ( n ) integers representing the array elements. All values in a test case are separated by spaces or newlines.

outputFormat

For each test case, output a single line. If a valid rearrangement exists, print the rearranged numbers separated by a single space. Otherwise, print -1. The outputs for different test cases should be printed on separate lines, and the output is written to standard output (stdout).## sample

3
4
1 2 3 4
5
1 3 5 7 9
6
10 11 10 12 11 12

1 2 3 4
-1
10 10 11 11 12 12