Kirei and the Linear Function

题意翻译

给一个对于 $v\left ( l,r \right ) $ 的定义:允许存在前导“$0$"的 $s\left [ l \right ] \sim s\left [ r \right ] $ 这一串数字。 有 $m$ 次询问，每次三个数: $l,r,k$。寻找两个子串 $\left ( L_{1}, L_{1}+w-1 \right ) $ 和 $\left ( L_{2}, L_{2}+w-1 \right )$ 且满足: $\bullet $ $L_{1}\ne L_{2}$ $\bullet\left ( v\left ( L_{1}, L_{1}+w-1 \right ) \cdot v\left ( l,r \right )+v\left ( L_{2}, L_{2}+w-1 \right ) \right ) mod $$9=k$ 可能出现多组答案，先保证 $L_{1}$ 最小，其次再保证 $L_{2}$ 最小。

题目描述

Given the string $ s $ of decimal digits (0-9) of length $ n $ . A substring is a sequence of consecutive characters of a string. The substring of this string is defined by a pair of indexes — with its left and right ends. So, each pair of indexes ( $ l, r $ ), where $ 1 \le l \le r \le n $ , corresponds to a substring of the string $ s $ . We will define as $ v(l,r) $ the numeric value of the corresponding substring (leading zeros are allowed in it). For example, if $ n=7 $ , $ s= $ "1003004", then $ v(1,3)=100 $ , $ v(2,3)=0 $ and $ v(2,7)=3004 $ . You are given $ n $ , $ s $ and an integer $ w $ ( $ 1 \le w < n $ ). You need to process $ m $ queries, each of which is characterized by $ 3 $ numbers $ l_i, r_i, k_i $ ( $ 1 \le l_i \le r_i \le n; 0 \le k_i \le 8 $ ). The answer to the $ i $ th query is such a pair of substrings of length $ w $ that if we denote them as $ (L_1, L_1+w-1) $ and $ (L_2, L_2+w-1) $ , then: - $ L_1 \ne L_2 $ , that is, the substrings are different; - the remainder of dividing a number $ v(L_1, L_1+w-1) \cdot v(l_i, r_i) + v(L_2, L_2 + w - 1) $ by $ 9 $ is equal to $ k_i $ . If there are many matching substring pairs, then find a pair where $ L_1 $ is as small as possible. If there are many matching pairs in this case, then minimize $ L_2 $ . Note that the answer may not exist.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — number of input test cases. The first line of each test case contains a string $ s $ , which contains only the characters 0-9 and has a length $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ). The second line contains two integers $ w, m $ ( $ 1 \le w < n, 1 \le m \le 2 \cdot 10^5 $ ), where $ n $ — is the length of the given string $ s $ . The number $ w $ denotes the lengths of the substrings being searched for, and $ m $ is the number of queries to be processed. The following $ m $ lines contain integers $ l_i, r_i, k_i $ ( $ 1 \le l_i \le r_i \le n $ , $ 0 \le k_i \le 8 $ ) — $ i $ th query parameters. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ . It is also guaranteed that the sum of $ m $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each request, print in a separate line: - left borders of the required substrings: $ L_1 $ and $ L_2 $ ; - -1 -1 otherwise, if there is no solution. If there are several solutions, minimize $ L_1 $ first, and minimize $ L_2 $ second.

输入输出样例

输入样例 #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

输出样例 #1

2 4
1 5
1 2
-1 -1
1 2
-1 -1
1 3
1 3
-1 -1
-1 -1
-1 -1

说明

Consider the first test case of example inputs. In this test case $ n=7 $ , $ s= $ "1003004", $ w=4 $ and one query $ l_1=1 $ , $ r_1=2 $ , $ k_1=1 $ . Note that $ v(1,2)=10 $ . We need to find a pair of substrings of length $ 4 $ such that $ v(L_1, L_1+3)\cdot10+v(L_2,L_2+3) $ has a remainder of $ k_1=1 $ when divided by $ 9 $ . The values $ L_1=2, L_2=4 $ actually satisfy all the requirements: $ v(L_1, L_1+w-1)=v(2,5)=30 $ , $ v(L_2, L_2+w-1)=v(4,7)=3004 $ . Indeed, $ 30\cdot10+3004=3304 $ , which has a remainder of $ 1 $ when divided by $ 9 $ . It can be shown that $ L_1=2 $ is the minimum possible value, and $ L_2=4 $ is the minimum possible with $ L_1=2 $ .

**题目大意：**
给定一个由十进制数字（0-9）组成的字符串s，长度为n。定义了一个子串v(l,r)为字符串s中从索引l到r的连续字符组成的数字（允许前导0）。例如，如果n=7，s="1003004"，则v(1,3)=100，v(2,3)=0，v(2,7)=3004。

给定n，s和一个整数w（1≤w
第i个查询的答案是长度为w的两个不同子串，分别表示为(L_1, L_1+w-1)和(L_2, L_2+w-1)，满足：
- L_1 ≠ L_2，即子串不同；
- 数字v(L_1, L_1+w-1) * v(l_i, r_i) + v(L_2, L_2 + w - 1)除以9的余数等于k_i。

如果存在多组答案，则优先使L_1最小，其次再使L_2最小。注意，答案可能不存在。

**输入输出格式：**
- 输入格式：
- 第一行包含一个整数t（1≤t≤10^4），表示输入测试用例的数量。
- 每个测试用例的第一行包含一个字符串s，只包含字符0-9，长度为n（2≤n≤2*10^5）。
- 第二行包含两个整数w, m（1≤w - 接下来的m行包含整数l_i, r_i, k_i（1≤l_i≤r_i≤n，0≤k_i≤8）——第i个查询的参数。
- 输出格式：
- 对于每个请求，单独一行输出：
- 所需子串的左边界：L_1和L_2；
- 如果没有解决方案，输出-1 -1。
如果存在多个解决方案，首先最小化L_1，其次最小化L_2。**题目大意：** 给定一个由十进制数字（0-9）组成的字符串s，长度为n。定义了一个子串v(l,r)为字符串s中从索引l到r的连续字符组成的数字（允许前导0）。例如，如果n=7，s="1003004"，则v(1,3)=100，v(2,3)=0，v(2,7)=3004。 给定n，s和一个整数w（1≤w