Вызов lower_bound:     

      int pos = lower_bound(dict.begin(),
                            dict.end(),
                            make_pair(pref, 0))
                - dict.begin();

В pos находим (дихотомией) в отсортированном словаре пар dict 
позицию слова пары со словом pref. 

14_FebB. AUTO
http://dl.gsu.by/task.jsp?nid=1270623&cid=15

Идея решения, вводим словарь и по ходу заносим в вектор слова и номера этих слов в словаре.
Сортируем слова по возрастанию (вместе с номерами).
Цикл по поисковым префиксам 
   Вводим префикс и его позицию k
   Дихотомией (с помощью lower bound) 
     ищем в словаре pos первое вхождение префикса
   Инкрементируем pos на k 
   Если полученная позиция в словаре, 
        а слово на этой позиции совпадает с префиксом
     Тогда выводим её
     Иначе выводим -1   

Подробнее о коде

      int pos = lower_bound(dict.begin(),
                            dict.end(),
                            make_pair(pref, 0))
                - dict.begin();

В pos находим (дихотомией) в отсортированном словаре позицию слова pref. 

      int poss = pos + k;
      if (poss < dict.size() && match(pref, dict[poss].first))
             cout << dict[poss].second + 1 << endl;
        else cout << -1 << endl;

если k-ое вхождение есть и соответствует pref, 
  тогда выводим исходный номер слова
  иначе вводим -1 

bool match(string pref, string word)
  {
    if (pref.size() > word.size()) return false;
    return word.substr(0, pref.size()) == pref;
  }

Соответствие слова из словаря word и искомого префикса pref
Выясняется с помощю булевой функции match

Далее приведен полный текст решения

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<pair<string, int> > dict;

bool match(string& pref, string& word)
  {
    if (pref.size() > word.size()) return false;
    return word.substr(0, pref.size()) == pref;
  }

int main()
{
  freopen("auto.in", "r", stdin);
  freopen("auto.out", "w", stdout);
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    {
      string s;
      cin >> s;
      dict.push_back(make_pair(s, i));
    }
  sort(dict.begin(), dict.end());
  for (int i = 0; i < m; i++)
    {
      int k; string pref;
      cin >> k >> pref;
      k--;
      int pos = lower_bound(dict.begin(),
                            dict.end(),
                            make_pair(pref, 0))
                - dict.begin();
      int poss = pos + k;
      if (poss < dict.size() && match(pref, dict[poss].first))
             cout << dict[poss].second + 1 << endl;
        else cout << -1 << endl;
    }
}