Лингвист анализирует текст и хочет узнать, как часто встречается каждая буква.

Дана строка из строчных латинских букв. Для каждой буквы, которая встречается в строке хотя бы один раз, выведите саму букву и количество её вхождений.

Результат нужно упорядочить по убыванию частоты. Если две буквы встречаются одинаковое число раз, их следует выводить в алфавитном порядке.

Входные данные

В единственной строке задана непустая строка из строчных латинских букв a–z, длиной до 200000.

Выходные данные

Для каждой встречающейся буквы выведите на отдельной строке букву, пробел и число её вхождений в указанном порядке.

Ограничения

• 1 <= длина строки <= 200000
• строка состоит только из строчных латинских букв a–z

Примеры

Пример 1

Входные данные

a

Выходные данные

a 1

Пример 2

Входные данные

abacaba

Выходные данные

a 4
b 2
c 1