PESADA06 - Quickly sort a list of integers

no tags 

Quickly sort the given list of integers. Quick is the key.

Input

The input begins with the number t, number of test cases in single line (t <= 10). Each test case begins with number n of input size (n <= 1000000) and n lines having n integers as input for the test case. Integers are signed integers in the range [-1000000, 1000000] and there can be duplicate entries.

Output

For every test case print the integers sorted in ascending order, one number per line. Test cases separated by an empty line.

Example

Input:
4
2
1234
-1234
1
4321
0
3
1000000
-1000000
100

Output:
-1234
1234

4321


-1000000
100
1000000

hide comments
pankaj joshi: 2015-03-19 22:34:45

hey anyone help me pls ....i m using quick sort it is giving tle

Petar Kovacev: 2015-02-17 16:06:51

Tricky one, TLE two times already, and I have been using quicksort-insertionsort combo...


Added by:Prof. Channa Bankapur
Date:2015-02-15
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C