Word Frequency Sorting

You are given a string consisting of words separated by spaces. Your task is to compute the frequency of each word and then output the results sorted in descending order of frequency. For words with the same frequency, sort them in ascending alphabetical order.

In other words, for each word \(w\) that appears in the input, determine its frequency \(f(w)\) and output each word alongside its frequency. The sorting order is defined such that for two words \(a\) and \(b\):

[ \text{if } f(a) \gt f(b) \text{ then } a \text{ comes before } b, \quad \text{if } f(a) = f(b) \text{ then the lexicographical order of } a \text{ and } b \text{ is used.} ]

This problem tests basic string manipulation and sorting techniques.

inputFormat

The input consists of a single line read from standard input (stdin) containing a string of words separated by spaces.

outputFormat

Output to standard output (stdout) the list of words and their frequencies. Each line should contain a word and its frequency separated by a space, following the sorted order described above.

## sample

the quick brown fox jumps over the lazy dog the quick cat

the 3
quick 2
brown 1
cat 1
dog 1
fox 1
jumps 1
lazy 1
over 1

</p>