Character Frequencies

Interview

Time limit1sMemory limit1024 MB

Summary

Count how many times each non-whitespace character appears in N lines of text and print each character with its count.

Level: Easy2 of 10
Topics: Hash map, String
Solved: No attempts yet

Problem

John is preparing a printing press for a publication. He needs to check that he has enough type pieces, the small blocks of cast metal with character shapes on them. Write a program that counts how many times each character appears in his text.

Input

The first line contains $N$ , the number of lines in John's publication ( $1 \le N \le 1\,000$ ). The next $N$ lines contain the text. Each line may consist of up to 100 characters. The text may contain uppercase and lowercase letters, digits, and punctuation marks.

Output

Print the frequency table of the characters that appear in the input text. On each line, print one character and its frequency (the number of times it appears in the text), separated by a space. The lines may be in any order. Spaces and line breaks are not counted as characters.

Examples1

Example 1

Input

4
A printing press is a mechanical device
for applying pressure to an inked surface
resting upon a print medium (such as paper
or cloth), thereby transferring the ink.

Expected output

( 1
) 1
, 1
. 1
A 1
a 10
b 1
c 6
d 3
e 15
f 3
g 4
h 5
i 12
k 2
l 3
m 3
n 12
o 5
p 9
r 14
s 10
t 8
u 5
v 1
y 2