Logo C++ Online Judge

C++

时间限制:3 s 空间限制:512 MB
TA:
统计

Given a list of words, print the k most frequent distinct words and their frequencies. Print more frequent words first. If two words occur equally often, print them in alphabetical order. If there are fewer than k distinct words, print all of them.

Input

The first line contains two integers n and k. The following n words are separated by spaces or line breaks. Each word consists of lowercase English letters.

  • 1 <= k <= n <= 200000
  • Each word contains between 1 and 20 letters.

Output

Print one line for each selected word, in the order described above. Each line contains the word, a space, and the number of times it occurs in the input.

Sample input

7 2
pear apple pear plum apple pear plum

Sample output

pear 3
apple 2

Both apple and plum occur twice. Only one fits after pear, so apple is printed.

Library note

You may use the C++ standard library. std::sort(first, last, comes_before) accepts a Boolean comparison function. It should return true when its first argument belongs strictly before its second, and false for equivalent arguments. The comparison must consistently define an ordering. The function can have a name; you do not need a lambda.

Sorting m elements takes O(m log m) comparisons. Looking up or inserting a key in std::map takes O(log m) comparisons when the map contains m keys. You do not need to implement these algorithms yourself.

Input performance

The input can be large. For faster input, use scanf, or place these lines at the start of main, before any input or output:

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

With synchronization disabled, use C++ streams consistently for input and output.