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 $ .