Задана строка \(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\).
Обратите внимание, что ответа может не существовать.
Выходные данные
Для каждого запроса в отдельной строке выведите:
- левые границы искомых подстрок: \(L_1\) и \(L_2\);
- -1 -1 в противном случае, если решения не существует.
Если решений несколько, минимизируйте в первую очередь \(L_1\), и во вторую очередь минимизируйте \(L_2\).
Примечание
Рассмотрим первый набор входных данных примера. В этом наборе \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|