An arrayof length is said to be good if the following conditions hold:
- For all ,
- for all .
You have an arrayof length ( ). You want to make the array good.
To do so, you can change atmostelements of .
Print the final array after changingto a good array. If there are multiple possible final arrays, print any of them.
It is guaranteed thatcan be made good after changing atmost elements of .
- The first line of input contains a single integer , denoting the number of test cases. The description of test cases follow.
- The first line of each test case contains an integer – the length of the array.
- The second line of each test case contains space-separated integers representing the initial array .
For each test case, output a single line containingspace-separated integers, denoting the elements of the final array after converting to a good array. The -th of these integers is -th element in the final array.
If multiple arrays exist which satisfy the conditions, print any of them.
Note: Final array should differ from original array at atmostindices.
- Sum of does not exceed over all testcases
Sample Input 1
2 3 6 12 5 3 5 5 5
Sample Output 1
6 12 8 5 5 5
Test Case 1: We can changeto . Now, is good since and . Hence, we made good after making only change which is .
Test Case 2: Arrayis already good.