Lyosha was sitting at the lecture. He was incredibly bored. The lecturer's voice seemed so distant and inconspicuous...
In order not to fall asleep completely, he took a piece of paper and wrote his favorite word on it. A little lower, he repeated his favorite word, without the first letter. Even lower, he again wrote his favorite word, but this time without the first and last letters.
Then the thought came to him — there is still a lot of time until the end of the lecture, why not continue writing this word in every possible way without some part from the beginning and some part from the end?
After the lecture, Lyosha told Max how wonderfully he had passed the time. Max became interested in counting how many letters of each type are found in Lyosha's leaflet. But unfortunately, the leaflet itself disappeared somewhere.
Max knows Lyosha's favorite word well, and he doesn't have as much free time as his friend, so help him quickly recover how many times Lyosha had to write down each letter.
Input
The input is a string consisting of lowercase Latin letters — Lyosha's favorite word.
The string length is between 5 and 100 000 characters.
Imprint
For each letter on Lyosha's piece of paper, print it, and then, separated by a colon and a space, how many times it occurs in the words Lesha wrote out (see the output format in the examples). The letters must be in alphabetical order. Letters that do not appear on the sheet do not need to be displayed.
Examples
| # |
Input |
Output |
| 1 |
hello |
e: 8
h:5
l: 17
o:5 |
| 2 |
abacaba |
a: 44
b: 24
c:16 |
Note
Explanation for the first example. If Lesha's favorite word — "hello", then the following words will be written on Lesha's piece of paper:
"hello"
"hell"
"ello"
"hel"
"ell"
"llo"
"he"
"el"
"ll"
"lo"
"h"
"e"
"l"
"l"
"o"
Among these words, the letter "e" occurs 8 times, 5 times — letter "h", 17 times — letter "l" and 5 times the letter "o".