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. Compute the frequency of each distinct substring.
3. Print the substrings according to their frequencies (high to low). If two substrings have the same frequency, print them in lexicographical order (alphabetical order).
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 final output should be
acc 3
abcu 2
efg 2
ac 1
Another example:
If the input is
2
fgcdab
fgdbca
The output should be
fg 2
ab 1
bc 1
cd 1
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 several lines of substrings and their occurrence frequencies (from high to low).
If two substrings have the same frequency, print them in lexicographical order (alphabetical order).
Each line contains a string and its occurrence frequency.
Each line has a newline character '\n' at the end. (Note that the last line also needs to be ended with a newline character.)