F. Кирей и линейная функция
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана строка $$$s$$$ из десятичных цифр (0-9) длины $$$n$$$.

Подстрока — это последовательность подряд идущих символов строки. Подстрока этой строки определяется парой индексов — своим левым и правым концами. Таким образом, каждой паре индексов ($$$l, r$$$), где $$$1 \le l \le r \le n$$$, соответствует подстрока строки $$$s$$$. Будем обозначать как $$$v(l,r)$$$ числовое значение соответствующей подстроки (в ней допускаются лидирующие нули).

Например, если $$$n=7$$$, $$$s=$$$«1003004», то $$$v(1,3)=100$$$, $$$v(2,3)=0$$$ и $$$v(2,7)=3004$$$.

Вам заданы $$$n$$$, $$$s$$$ и целое число $$$w$$$ ($$$1 \le w < n$$$).

Вам необходимо обработать $$$m$$$ запросов, каждый из которых характеризуется $$$3$$$ числами $$$l_i, r_i, k_i$$$ ($$$1 \le l_i \le r_i \le n; 0 \le k_i \le 8$$$).

Ответом на $$$i$$$-й запрос является такая пара подстрок длины $$$w$$$, что если обозначить их как $$$(L_1, L_1+w-1)$$$ и $$$(L_2, L_2+w-1)$$$, то:

  • $$$L_1 \ne L_2$$$, то есть подстроки различны;
  • остаток при делении числа $$$v(L_1, L_1+w-1) \cdot v(l_i, r_i) + v(L_2, L_2 + w - 1)$$$ на $$$9$$$ равен $$$k_i$$$.

Если существует много подходящих пар подстрок, то найдите такую пару, где $$$L_1$$$ как можно меньше. Если и в этом случае существует много подходящих пар, то минимизируйте $$$L_2$$$.

Обратите внимание, что ответа может не существовать.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первой строкой набора входных данных является $$$s$$$, которая содержит только символы 0-9 и имеет длину $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

Вторая строка содержит два целых числа $$$w, m$$$ ($$$1 \le w < n, 1 \le m \le 2 \cdot 10^5$$$), где $$$n$$$ — это длина заданной строки $$$s$$$. Число $$$w$$$ обозначает длины искомых подстрок, а $$$m$$$ – количество запросов для обработки.

Следующие $$$m$$$ строк содержат целые числа $$$l_i, r_i, k_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$0 \le k_i \le 8$$$) — параметры запроса $$$i$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$. Также гарантируется, что сумма $$$m$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого запроса в отдельной строке выведите:

  • левые границы искомых подстрок: $$$L_1$$$ и $$$L_2$$$;
  • -1 -1 в противном случае, если решения не существует.

Если решений несколько, минимизируйте в первую очередь $$$L_1$$$, и во вторую очередь минимизируйте $$$L_2$$$.

Пример
Входные данные
5
1003004
4 1
1 2 1
179572007
4 2
2 7 3
2 7 4
111
2 1
2 2 6
0000
1 2
1 4 0
1 4 1
484
1 5
2 2 0
2 3 7
1 2 5
3 3 8
2 2 6
Выходные данные
2 4
1 5
1 2
-1 -1
1 2
-1 -1
1 3
1 3
-1 -1
-1 -1
-1 -1
Примечание

Рассмотрим первый набор входных данных примера. В этом наборе $$$n=7$$$, $$$s=$$$«1003004», $$$w=4$$$ и один запрос $$$l_1=1$$$, $$$r_1=2$$$, $$$k_1=1$$$. Заметим, что $$$v(1,2)=10$$$. Надо найти такую пару подстрок длины $$$4$$$, что $$$v(L_1, L_1+3)\cdot10+v(L_2,L_2+3)$$$ имеет остаток $$$k_1=1$$$ при делении на $$$9$$$. Значения $$$L_1=2, L_2=4$$$ в самом деле удовлетворяют всем требованиям: $$$v(L_1, L_1+w-1)=v(2,5)=30$$$, $$$v(L_2, L_2+w-1)=v(4,7)=3004$$$. Действительно, $$$30\cdot10+3004=3304$$$, что имеет остаток $$$1$$$ при делении на $$$9$$$. Можно показать, что $$$L_1=2$$$ — минимальное возможное значение, а $$$L_2=4$$$ — минимальное возможное при $$$L_1=2$$$.