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 testcases k (k< 100). Every testcase c onsists of n+1 (1< n< 50000) lines. Each line contains of a string of 10 character s. The first line of each testcase 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
La Van Tien: 2017-04-01 19:13:52

oops!

Last edit: 2017-04-01 19:14:41
Avi Aryan: 2015-10-29 15:26:44

sort over string vector works too 0.03s

Abhinandan Agarwal: 2015-05-30 01:54:56

And improved implementation of radix sort through structures gave 0.01s . Still waiting for 0.00s ...

Last edit: 2015-05-30 02:09:14
ankur : 2015-01-02 13:46:40

i am getting WA, i have checked it on hundreds of different cases on ideone, but no idea

Shubham Singh: 2014-11-25 05:16:26

poor documentation of problem. what is n and c.

Kaushik: 2014-04-11 14:57:31

STL MAP :D

Changming: 2013-07-04 03:17:26

Quick Sort is enough for this problem.

Chandan Singh: 2013-06-28 19:01:52

you can use quick sort.

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:0.992s
Source limit:8083B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET