Top K Frequent

Lab C++ Advanced 30 points

Read n words and k. Print the k most frequent words (ties alphabetical) as word count, using a map for counting and a priority queue of pairs.

Input

n, the words, then k.

Output

k lines.

Example

Input

10
b a c a b a d d d d
2

Output

d 4
a 3

Sample input available Sample output available

Editor

C++

Hints

A custom comparator defines what 'top' means.

decltype(lambda) is the comparator's type.

Solution explanation

The comparator returns true when its first argument has lower priority.

Show solution

#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n;
    map<string, int> counts;
    for (int i = 0; i < n; i++) {
        string w;
        cin >> w;
        counts[w]++;
    }
    cin >> k;
    auto worse = [](const pair<int, string> &a, const pair<int, string> &b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second;
    };
    priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(worse)> pq(worse);
    for (const auto &[w, c] : counts) pq.push({c, w});
    for (int i = 0; i < k && !pq.empty(); i++) {
        cout << pq.top().second << " " << pq.top().first << "\n";
        pq.pop();
    }
    return 0;
}

Output

Answer