Character Frequency Sorting

You are given a string and your task is to compute the frequency of each character in the string. Then, you must print each unique character along with its frequency. The output should be sorted primarily in descending order of frequency and, for characters with equal frequency, in ascending lexicographical order.

Example:

Input: tree
Output:
  e 2
  r 1
  t 1

Note: The input is read from stdin and the output is printed to stdout.

inputFormat

The input consists of a single line containing the string.

outputFormat

For each unique character in the string, print a line with the character and its frequency separated by a space. The lines must be sorted in descending order of frequency, and for equal frequencies, in ascending lexicographical order.

## sample

tree

e 2
r 1
t 1

</p>