Letter Frequency

Interview

Time limit1sMemory limit1024 MB

Summary

Given up to 20 lowercase words, find the most frequent letter at each position, listing all tied letters in alphabetical order.

Level: Easy3 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

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 \le n \le 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, in the format shown in the sample output. 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.

Examples2

Example 1

Input

5
this
is
an
example
ink

Expected output

1: i
2: n
3: a i k
4: m s
5: p
6: l
7: e

Example 2

Input

3
this
is
longlonglong

Expected 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