Count Word Frequencies

This problem requires you to count the frequency of each distinct word from a given list of words. You will be provided with an integer n representing the number of words followed by n words separated by spaces. Your task is to output each distinct word along with its frequency, with the words sorted in lexicographical order.

For example, given the input:

6
apple banana apple orange banana apple

The correct output is:

apple 3
banana 2
orange 1

Note: If the input list is empty (i.e. n = 0), no output should be produced.

The frequency calculation can be expressed mathematically as follows:

\[ \text{frequency}(w) = \sum_{i=1}^{n} \delta(w, s_i) \] where \( \delta(w, s_i) = 1 \) if \( w = s_i \) and \(0\) otherwise.

inputFormat

The first line contains an integer n (0 ≤ n ≤ 10⁵), representing the number of words.

The second line contains n space-separated words. Each word consists of lowercase English letters.

outputFormat

For each distinct word, output a line containing the word and its frequency separated by a space. The words must be printed in lexicographical (alphabetical) order.

If n is 0, no output should be produced.

## sample

6
apple banana apple orange banana apple

apple 3
banana 2
orange 1

</p>