Сказители «Манаса»
Эпос «Манас» — один из самых длинных эпосов в мире: самые полные записи, сделанные со слов сказителей-манасчы, содержат сотни тысяч стихотворных строк. Студенты-филологи ОшГУ оцифровывают запись одного из сказителей и строят по ней электронный указатель.
Текст записан латиницей без пробелов и знаков препинания: это строка s длины n из строчных латинских букв. Фрагментом назовём любую непустую подстроку s[l..r]. Одинаковые подстроки, встречающиеся в разных местах, считаются одним фрагментом.
Все различные фрагменты выписали в указатель в лексикографическом (словарном) порядке. Поступает q запросов: для заданного k найдите k-й фрагмент указателя и выведите его самое левое вхождение в текст — пару l r, такую что s[l..r] равна этому фрагменту и l минимально. Если в указателе меньше k фрагментов, выведите -1.
Напомним, что строка a лексикографически меньше строки b, если a — собственный префикс b или в первой различающейся позиции буква a идёт в алфавите раньше.
Входные данные
В первой строке — два целых числа n и q (1 ≤ n, q ≤ 300 000).
Во второй строке — строка s из n строчных латинских букв.
В третьей строке — q целых чисел k (1 ≤ k ≤ 10¹²).
Выходные данные
Для каждого запроса выведите в отдельной строке два числа l r (нумерация букв с единицы) или -1.
Пример 1
Вход:
5 6
manas
1 4 5 11 14 15
Выход:
2 2
2 5
4 5
3 3
5 5
-1
Пояснение
Различные фрагменты строки manas в словарном порядке: a, an, ana, anas, as, m, ma, man, mana, manas, n, na, nas, s — всего 14. Фрагмент a встречается дважды, самое левое вхождение — s[2..2]. Пятнадцатого фрагмента нет.
Система оценивания
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 15 | n ≤ 60 |
| 2 | 25 | n ≤ 5000, q ≤ 3000 |
| 3 | 60 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Комментарии