PESADA06 - Quickly sort a list of integers

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

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

hide comments
2015-03-19 22:34:45 pankaj joshi
hey anyone help me pls ....i m using quick sort it is giving tle
2015-02-17 16:06:51 Petar Kovacev
Tricky one, TLE two times already, and I have been using quicksort-insertionsort combo...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.