PCPC12D - New Strategy

no tags 

Meeda will compete this year in the ACM-ICPC world finals, but he is a crazy guy, he created a new strategy to attack the problem set. His new strategy is to solve the problems according to their names. He’ll sort the problem set according to the following rules.

  • Remove all whitespace characters from the problem names.
  • Replace any capital letters with the corresponding small one. i.e ‘A’ will be ‘a’.
  • count the occurrence of each character.
  • Problem A comes before problem B, if A contains lexicographically smaller characters more than B i.e A = “cba” comes before B = “bc” because A contains 1 'a' and B contains 0 'a'.

But as you may know that meeda is a very lazy guy and he needs to train for this strategy before the world finals, so he needs your help to write an efficient program to help him in the training.

Input

The first line of the input contains T, number of test cases, each test case starts with an integer n (0 < n < 1000) number of problems, follow n lines each containing string s. The ith line is the name of the ith problem. s will be a sequence of characters (a-z, A-Z or any white space character), length of s is less than 200 characters.

Output

First line of each test case should contains “case: ” without double quotes followed by the test case number starting from 1, then follow problem names sorted as described above.

Input
2
2
abc
ab
4
bcsaasd
dbasaaaa
azzz
bayy

Output
case: 1
abc
ab
case: 2
dbasaaaa
bcsaasd
bayy
azzz

note: sorry for the wrong description.

Max length is 200.


hide comments
Momontho Mashak Monmoy: 2013-01-15 15:34:17

There are some invalid test cases in the input file : cases with n>1000 and/or |s|>100

Robert Gerbicz: 2013-01-15 15:34:17

"what to print if both have the equal number of each characters" in that case keep the original ordering of the two strings (there are such cases in the input).

Swapnil R.Mehta: 2013-01-15 15:34:17

@adityapande
i m also getting the same output for your test case but still getting WA!

Aditya Pande: 2013-01-15 15:34:17

why is submission id 8368920 and 8368947(8368908
836891) getting WA?
what to print if both have the equal number of each characters
eg: input:
1
3
bcz
zbc
cbz


>output :
case: 1
bcz
zbc
cbz


>>>getting every test case right, still WA ( 8369111 )

Last edit: 2013-01-01 10:28:47

Added by:abdelkarim
Date:2012-12-28
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:The First Palestinian Collegiate Programming Contest