C. Letter Frequency
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The most common consonants in English are R, T, N, S, and L. The most common vowels are E, A, and I. It is definitely fun to find the most common letters.

Given a set of words, find the letter that occurs the most in each position. That is, the most frequent letter at Position 1 when considering all the words, the most frequent letter at Position 2 when considering all the words, etc. If more than one letter is the most frequent for a particular position (i.e., ties for max at that position), print those letters in alphabetical order.

Input

The first input line contains an integer, $$$n$$$ $$$(1 ≤ n ≤ 20)$$$, indicating the number of words. Each of the next $$$n$$$ input lines contains a word. Assume that each word contains $$$1$$$-$$$30$$$ lowercase letters and it starts in column one.

Output

Print each position and the letter(s) that occur the most in that position, following the format illustrated in Sample Output. Note that each output line starts with a number, immediately followed by a colon (':'), followed by a space, followed by a letter. If there are multiple letters for an output line, they are separated by exactly one space.

Examples
Input
5
this
is
an
example
ink
Output
1: i
2: n
3: a i k
4: m s
5: p
6: l
7: e
Input
3
this
is
longlonglong
Output
1: i l t
2: h o s
3: i n
4: g s
5: l
6: o
7: n
8: g
9: l
10: o
11: n
12: g