Нудна лекція
Льоша сидів на лекції, і йому було неймовірно нудно. Голос лектора здавався таким далеким і непомітним...
Щоб не заснути, він взяв аркуш паперу і написав на ньому своє улюблене слово. Трохи нижче він повторив це слово, але без першої літери. Ще нижче він знову написав своє улюблене слово, але цього разу без двох перших і останньої літери.
Тут йому спала на думку ідея: часу до кінця лекції ще багато, чому б не продовжити виписувати це слово всіма можливими способами, видаляючи якусь частину з початку і якусь частину з кінця?
Після лекції Льоша розповів Максу, як цікаво він скоротив час. Максу стало цікаво підрахувати, скільки разів кожна літера зустрічається у Льоші на аркуші. Але, на жаль, сам аркуш десь загубився.
Макс добре знає улюблене слово Льоші, але у нього не так багато вільного часу, як у його друга, тому допоможіть йому швидко визначити, скільки разів Льоша виписав кожну літеру.
Вхідні дані
Один рядок, що складається з малих латинських літер — улюблене слово Льоші. Довжина рядка знаходиться в межах від 5 до 10^5 символів.
Вихідні дані
Для кожної літери на аркуші Льоші виведіть її, а потім через двокрапку і пробіл вкажіть, скільки разів вона зустрілася у виписаних Льошею словах (як показано в прикладах). Літери повинні бути в алфавітному порядку. Літери, що не зустрічаються на аркуші, виводити не потрібно.