The input contains N strings (0 < N < 100). Each string consists of at most 9 lowercase letters.
1. Find the longest nondecreasing substring(s) of each string. (There might be more than one longest nondecreasing substring.)
2. Count the number of occurrences (frequency) of each distinct substring.
3. Sort the substrings according to their frequencies (high to low). If two substrings have the same frequency, sort them in lexicographical order (alphabetical order).
4. Use the ranking of each substring as its score. E.g., the first one gets 1 point, the second gets 2 points, and so on.
5. Use the scores of substrings to re-evaluate the original input string and print the total score of each input string.
[Example]
For example, the input may be
7
xxaccb
xabcud
yyxacc
efgacc
tsefgab
aca
rqabcud
The longest nondecreasing substrings are
acc
abcu
acc
efg acc
efg
ac
abcu
The frequencies are
abcu 2
ac 1
acc 3
efg 2
The sorted order should be
acc 3
abcu 2
efg 2
ac 1
Their scores are
acc 1
abcu 2
efg 3
ac 4
The re-evaluation results are
xxaccb 1 (because acc gets 1 point)
xabcud 2 (because abcu gets 2 points)
yyxacc 1 (because acc gets 1 point)
efgacc 4 (because efg gets 3 points and acc gets 1 point)
tsefgab 3 (because efg gets 3 points)
aca 4 (because ac gets 4 points)
rqabcud 2 (because abcu gets 2 points)
Another example: If the input is
2
fgcdab
fgdbca
The longest nondecreasing substrings are
fg cd ab
fg bc
The frequencies are
fg 2
cd 1
ab 1
bc 1
The sorted order should be
fg 2
ab 1
bc 1
cd 1
Their scores are
fg 1
ab 2
bc 3
cd 4
The re-evaluation results are
fgcdab 7 (fg gets 1 point, cd gets 4 points, and ab gets 2 points)
fgdbca 4 (fg gets 1 point and bc gets 3 points)
The first line of input is an integer N indicating the number of input strings. (0 < N < 100)
The next N lines are the input strings. Each string consists of at most 9 lowercase letters.
The output contains N lines of strings and their scores. The strings are listed as their original input order.
Each line contains a string and its score.
Each line has a newline character at the end. (Note that the last line also needs to be ended with a newline character.)