Скучная лекция
Леша сидел на лекции. Ему было невероятно скучно. Голос лектора казался таким далеким и незаметным...
Чтобы окончательно не уснуть, он взял листок и написал на нем свое любимое слово. Чуть ниже он повторил свое любимое слово, без первой буквы. Еще ниже он снова написал свое любимое слово, но в этот раз без двух первых и последней буквы.
Тут ему пришла в голову мысль - времени до конца лекции все равно еще очень много, почему бы не продолжить выписывать всеми возможными способами это слово без какой-то части с начала и какой-то части с конца?
После лекции Леша рассказал Максу, как замечательно он скоротал время. Максу стало интересно посчитать, сколько букв каждого вида встречается у Леши в листочке. Но к сожалению, сам листочек куда-то запропастился.
Макс хорошо знает любимое слово Леши, а еще у него не так много свободного времени, как у его друга, так что помогите ему быстро восстановить, сколько раз Леше пришлось выписать каждую букву.
Входные данные
Одна строка, состоящая из строчных латинских букв - любимое слово Леши. Длина строки лежит в пределах от 5 до 10^5 символов.
Выходные данные
Для каждой буквы на листочке Леши, выведите ее, а затем через двоеточие и пробел сколько раз она встретилась в выписанных Лешей словах (как показано в в примерах). Буквы должны следовать в алфавитном порядке. Буквы, не встречающиеся на листочке, выводить не нужно.