SLEXSORT - Lexicographic sort


Given alphabet A and a list of words, sort the list according to the lexicographic order induced by A.

Input

The first line of input contains t, the number of tests.

Each test begins with a line with alphabet A, which consists of lowercase letters arbitrary chosen from the Latin alphabet. The next line contains an integer n<100 000 - the number of words. The subsequent n contain one word each, which is not longer than 1 000 letters. Additionally, you can assume that the total number of letters in all words of each test does not exceed 4*106.

There is an empty line after each test.

Output

For each test output the sorted list of words in successive lines.

Score

The score is equal to the length of the source code of your program.

Example

Input:
2
re
3
ere
rer
re

balujemy
5
bel
luba
lej
bal
leje

Output:
re
rer
ere

bal
bel
luba
lej
leje
Warning: large Input/Output data, be careful with certain languages

hide comments
rama_krishna1: 2018-02-20 17:36:30

Will there be a new line character after every test case, even after the last test case? If I get a runtime error in Python3 where can we find out which line is causing it? I used ideone but my code is doing good there but giving runtime error while my code is run by judge.

to_test: 2014-02-28 09:54:35

how do i make space for 100000 words in memory??

Aditya Pande: 2012-12-27 10:11:38

got AC in C++ in 1.2 seconds
EDIT:
----> why am i getting TLE with my RUBY solution
submission ID 8356336. Aren't the .tr() and .sort() fast enough. I guess it should get AC because sort should be O(n log n) in RUBY...

Last edit: 2013-01-02 08:54:59
Jander: 2011-11-17 13:26:06

68 for Perl now too :-)

Piotr KÄ…kol: 2011-01-15 17:06:46

The shortest code has no 71 characters anymore. It's 70 chars in Ruby. ;-)

Edit: Now the record is even 69 (yes, 69, You nasty :P) in Perl by Jander.

Edi2: And again Ruby wins with 68 bytes by HWK!

Last edit: 2011-09-23 15:58:18

Added by:kuszi
Date:2007-04-10
Time limit:30s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET