# include <cstdio>
# include <queue>
# include <cmath>
# include <iostream>
# include <vector>
# include <cstdlib>
# include <ctime>
# include <algorithm>
# include <utility>
using namespace std;


/*
1. структура для кучи отрезок + макс
2. приориту кью
3. segment_tree с возвратом максимума на отрезке
4. класс suggest

*/

struct NumberOfRequests
{
    int count;
    int i;
}

struct heap {
    int left;
    NumberOfRequests max;
    int right;

    bool operator < (const heap &a) const
    {
        return max.count < a.max.count;
    }
    bool operator > (const heap &a) const
    {
        return max.count > a.max.count;
    }
    bool operator == (const heap &a) const
    {
        return max.count ==a.max.count;
    }
}

class SegmentTree {
    vector <NumberOfRequests> tree;
    int size;
    NumberOfRequests _subMax (int v, int L, int R, int l, int r) // L и R это за какой отрезок отвечает v; l и r - запрос
    {
        NumberOfRequests answer;
        answer.count = 0;
        answer.i = - 1;
        if (l > r) return answer;
        if (l == L && r == R)
        {
            tree[v].i = v - size + 1;
            return tree[v];
        }
        return max (_subMax(2 * v + 1, L, (L + R) / 2, l, min(r, (L+R) / 2)),
                    _subMax(2 * v + 2, (L + R)/ 2 + 1, R, max(l, (L+R) / 2 + 1), r));
    }

    public :
    SegmentTree (const vector <NumberOfRequests > &a)
    {
        for (size = 1; size < a.size(); size *= 2);
        int tmp = size;
        NumberOfRequests answer;
        answer.count = 0;
        answer.i = - 1;
        tree.assign(2 * size - 1, answer);
        for (int i = 0; i < a.size(); i++)
        {
            tree[size - 1 + i].count = a[i].count;
            tree[size - 1 + i].i = i;
        }

        for (int i = size - 2; i >= 0; i--)
            tree[i] = max(tree[2 * i + 1], tree[2 * i + 2]);
        size = tmp;
    }

    NumberOfRequests subMax(int l, int r)
    {
        return _subMax(0, 0, size - 1, l, r);
    }


}

class Suggest {
    vector <NumberOfRequests > tree;
    vector <int> answer_number;
    priority_queue <heap> q;
    vector <pair <string, int> > data;

    Suggest (const vector <pair <string, int> > &array)
    {
        data = vector <pair < string, int> > (array.begin(), array.end());
        sort(data.begin(), data.end());
        int l = data.size();
        for (int i = 0; i < l; i++)
        {
            tree[i].i = i;
            tree[i].count = data[i].second;
        }
        SegmentTree ST(tree); //// &
    }
    void Request (string& s, int counter, vector <int> &answer_number)
    {
        vector<pair <string, int> >::iterator li, ri;
        li = lower_bound(data.begin(), data.end(), make_pair(s, 0));
        ri = upper_bound(data.begin(), data.end(), make_pair(s, 100000000));
        int l = li - data.begin();
        int r = ri - data.begin();
        r--;
        heap tmp;
        void fillingHeap (int left, int right, int counter)
        {
            if (l > r || counter == 0) return;
            /*if (!q.empty)
            {
                tmp = q.top()
                answer_number.push_back(tmp.max.i)
                q.pop();
            }*/
            tmp.left = l;
            tmp.max = ST.subMax(l, r);
            tmp.right = r;
            q.push(tmp);
            fillingHeap(l, maximum.second - 1, counter - 1);
            fillingHeap(maximum.second + 1, r, counter - 1);
        }
        for (int i = 0; i < counter && !q.empty(); i++)
        {
            tmp = q.top();
            answer_number.push_back(tmp.max.i);
            q.pop();

        }
    }
}