Word Count Engine

You are given a text and an integer k. Your task is to count the occurrences of each word in the text (ignoring case) and then output the top k most frequent words. When words have the same frequency, sort them in lexicographical order (i.e. alphabetically). The word matching should be case-insensitive and words are defined as sequences of alphanumeric characters.

Formally, let the text be a string T and let wi be a word in T. The frequency of a word w is given by:

\( f(w) = \#\{ w_i \in T : \text{lower}(w_i) = w \} \)

Your job is to output the top k words sorted by descending frequency and lexicographically increasing order when frequencies tie.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains the text which may include punctuation.
2. The second line contains a single integer k indicating the number of top frequent words to display.

Note: The text can be assumed to be non-empty and k a positive integer.

outputFormat

Output to stdout the top k words and their frequencies. Each line should contain a word and its frequency separated by a space. The words must be ordered by decreasing frequency, and if two words have the same frequency, they should be ordered in lexicographical order.

## sample

The sun shines over the lake. The sun also rises.
3

the 3
sun 2
also 1

</p>