Description

Remember to print the result in your function.c as the printf part is commented on the partial judge code.

Robin stumbled arcross split poneglyphs on a ship, but she still couldn't understand the meaning behind them.

Ace, Luffy's brother, came to the ship and noticed the split poneglyphs.

He demonstrated to Robin with his fire fist that by splitting the string into words and sorting the alphabet in each word in decreasing order based on character frequency, a hidden clue could be revealed.

The rules to sort the characters in the string are:

- Sort the characters by how frequently they appear in the string. If they appear more frequently, they should come first.

- If the frequency of characters is the same, sort it by the type, namely from uppercases  > lowercases > digits.

- If the type is also the same, sort uppercase and lowercase characters in dictionary order, and sort digits in increasing order.

Take the string "IxyzamxyzluffyxyzaAbb54xyztree" for example. If it were to be split using the delimiter "xyz", the set of words from the splitting process is ["I", "am", "luffy", "aAbb54", "tree"].

After sorting each alphabet in the words, we obtain ['I', 'am', 'ffluy','bbAa45', 'eert'].

Explanation:

 "aAbb54" -> "bbAa45"

 'b' appears twice while 'a', 'A', '5', and '4' appear once. So 'b' must appear before 'a', 'A', '5', and '4'. Next, since the order of precedence is uppercase letters > lowercase letters > digits, 'A' must appear before 'a', '5', and '4', and 'a' must appear before '5' and '4'. Finally since '5' and '4' have the same frequency then sort it by increasing order.

"tree" -> "eert"

 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. And 'r' is before 't' since it is like so in dictionary order

ps: you should print by yourself at the sort function

Input

The first line contains a string S that should be split, 20 ≤ the length of S ≤ 499

The second line is the delimiter string P, 1 ≤ the length of P ≤ 9.

Output

Output the sorted strings splited by the given pattern.

Don't forget to include '\n' at the end of each output string.

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

14153.c

Partial Judge Header

14153.h

Tags

Discuss

Description

Let str be a string, we define a function f(str) as follows: the number of substrings of str where all characters in each substring are the same.

For example, f(s) = 5, where s='aabc'. The substrings where all characters are the same are: s[0,0]='a', s[1,1]='a', s[0,1]='aa', s[2,2]='b', and s[3,3]='c'.

Now, given a string s, you need to find a subsequence s' of s such that f(s') is maximized. A subsequence of a string is formed by deleting some characters from the string without changing the order of the remaining characters. For example, "chy" and "cye" are subsequences of "chyen", but "cey" is not.

 

Input

The first line of the input is an integer T, denoting the number of testcases. 1<= T <= 10

Next T lines indicate T strings s to find such subsequence.

1 <= length of s <= 20

Note that s only contains lowercase English alphabets.

Output

For each testcase, let s' be the subsequence of s that maximize f(s'). Output f(s').

Remember to output '\n' at the end of each line.

 

Hint

In the sample testcase 1, s'='aaa'. In the sample testcase 2, s'='abbb'.

Sample Input  Download

Sample Output  Download

Tags

Discuss