Final: Top k Words

Lab Python Intermediate 20 points

Read a paragraph and k. Print the k most frequent words (ignore capital letters) with their counts, most frequent first; ties are broken alphabetically. Words are separated by spaces and contain only letters.

Input

Line 1: the text. Line 2: k.

Output

k lines: <word> <count>.

Example

Input

the day is sunny the the the sunny is is
4

Output

the 4
is 3
sunny 2
day 1

Sample input available Sample output available

Editor

Python

Hints

Count with a dict or Counter.

Sort by (-count, word) and take the first k.

Solution explanation

Hashing to count, then sorting with a tuple key: O(n + u log u) for u different words.

Show solution

from collections import Counter
words = input().lower().split()
k = int(input())
c = Counter(words)
for w, n in sorted(c.items(), key=lambda t: (-t[1], t[0]))[:k]:
    print(w, n)

Output

Answer