eolymp
bolt
Try our new interface for solving problems
Problems

Boring lecture

Boring lecture

Time limit 1 second
Memory limit 128 MiB

Lesha sat on a lecture. He was incredibly boring. The lecturer's voice seemed so far away and unnoticeable ...

In order not to fall asleep completely, he took a piece of paper and wrote his favorite word on it. Just below, he repeated his favorite word, without the first letter. Below, he wrote his favorite word again, but this time without the first two and the last letter.

Then a thought came to his mind - there is still a lot of time until the end of the lecture, why not continue to write out this word in every possible way without some part from the beginning and some part from the end?

After the lecture, Alex told Max how wonderful he was in passing the time. Max was interested in counting how many letters of each type are found in Lesha's piece of paper. But unfortunately, the paper has disappeared somewhere.

Max knows well Lesha's favorite word, and he doesn't have as much free time as his friend, so help him to quickly recover how many times Lesha had to write out each letter.

Input data

One line consisting of lowercase Latin letters is Lesha's favorite word. The length of the string is from 5 to 100 000 symbols.

Output data

For each letter on Lesha's paper, print it out, and then after the colon and a space print how many times it appears in the words written by Lesha (see the output format in the examples). Letters must be ordered in alphabetical order. Letters that are not found on a piece of paper do not print.

Examples

Input example #1
hello
Output example #1
e: 8
h: 5
l: 17
o: 5
Input example #2
abacaba
Output example #2
a: 44
b: 24
c: 16
Source 2013 Moscow city informatics olympiad for 6-9 classes, Moscow, February 3, Problem С