LEXISORT - Easy Sorting

no tags 

Given is a list of words and a lexicographical ordering according to the ascii alphabet. Your task is to sort the words in increasing order.

Input

The first line contains the numbers of test cases k (k< 100). Every test case consists of n+1 (1 < n < 50000) lines. Each line contains of a string of 10 characters. The first line of each test case contains n.

Output

Output the sorted list of words.

Example

Input:
2
2
helloworld
worldhello
2
aaaaaaaaaa
Aaaaaaaaaa

Output:
helloworld
worldhello
Aaaaaaaaaa
aaaaaaaaaa

hide comments
Arkadiusz Bulski: 2012-08-16 17:28:49

O(n) time complexity is probably necessary, so radix sort and by extension count sort.

ria yunita sari: 2012-05-05 05:12:38

what sorting is used for this problem? (time limit exceeded)


Added by:Simon
Date:2005-04-13
Time limit:1s
Source limit:8083B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET