Сказители «Манаса»


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 512M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Эпос «Манас» — один из самых длинных эпосов в мире: самые полные записи, сделанные со слов сказителей-манасчы, содержат сотни тысяч стихотворных строк. Студенты-филологи ОшГУ оцифровывают запись одного из сказителей и строят по ней электронный указатель.

Текст записан латиницей без пробелов и знаков препинания: это строка 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 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.


Комментарии

Еще нет ни одного комментария.