Codeforces Round #820 (Div. 3) F

F. Kirei and the Linear Function

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Given the string ss of decimal digits (0-9) of length nn.

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,rl,r), where 1≤l≤r≤n1≤l≤r≤n, corresponds to a substring of the string ss. We will define as v(l,r)v(l,r) the numeric value of the corresponding substring (leading zeros are allowed in it).

For example, if n=7n=7, s=s=”1003004″, then v(1,3)=100v(1,3)=100, v(2,3)=0v(2,3)=0 and v(2,7)=3004v(2,7)=3004.

You are given nn, ss and an integer ww (1≤w<n1≤w<n).

You need to process mm queries, each of which is characterized by 33 numbers li,ri,kili,ri,ki (1≤li≤ri≤n;0≤ki≤81≤li≤ri≤n;0≤ki≤8).

The answer to the iith query is such a pair of substrings of length ww that if we denote them as (L1,L1+w−1)(L1,L1+w−1) and (L2,L2+w−1)(L2,L2+w−1), then:

• L1≠L2L1≠L2, that is, the substrings are different;
• the remainder of dividing a number v(L1,L1+w−1)⋅v(li,ri)+v(L2,L2+w−1)v(L1,L1+w−1)⋅v(li,ri)+v(L2,L2+w−1) by 99 is equal to kiki.

If there are many matching substring pairs, then find a pair where L1L1 is as small as possible. If there are many matching pairs in this case, then minimize L2L2.

Note that the answer may not exist.

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104) — number of input test cases.

The first line of each test case contains a string ss, which contains only the characters 0-9 and has a length nn (2≤n≤2⋅1052≤n≤2⋅105).

The second line contains two integers w,mw,m (1≤w<n,1≤m≤2⋅1051≤w<n,1≤m≤2⋅105), where nn — is the length of the given string ss. The number ww denotes the lengths of the substrings being searched for, and mm is the number of queries to be processed.

The following mm lines contain integers li,ri,kili,ri,ki (1≤li≤ri≤n1≤li≤ri≤n, 0≤ki≤80≤ki≤8) — iith query parameters.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105. It is also guaranteed that the sum of mm over all test cases does not exceed 2⋅1052⋅105.

Output

For each request, print in a separate line:

• left borders of the required substrings: L1L1 and L2L2;
• -1 -1 otherwise, if there is no solution.

If there are several solutions, minimize L1L1 first, and minimize L2L2 second.

Example

input
Copy

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

output
Copy

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

Note

Consider the first test case of example inputs. In this test case n=7n=7, s=s=”1003004″, w=4w=4 and one query l1=1l1=1, r1=2r1=2, k1=1k1=1. Note that v(1,2)=10v(1,2)=10. We need to find a pair of substrings of length 44 such that v(L1,L1+3)⋅10+v(L2,L2+3)v(L1,L1+3)⋅10+v(L2,L2+3) has a remainder of k1=1k1=1 when divided by 99. The values L1=2,L2=4L1=2,L2=4 actually satisfy all the requirements: v(L1,L1+w−1)=v(2,5)=30v(L1,L1+w−1)=v(2,5)=30, v(L2,L2+w−1)=v(4,7)=3004v(L2,L2+w−1)=v(4,7)=3004. Indeed, 30⋅10+3004=330430⋅10+3004=3304, which has a remainder of 11 when divided by 99. It can be shown that L1=2L1=2 is the minimum possible value, and L2=4L2=4 is the minimum possible with L1=2L1=2.

分析：

这题和数字根有关，数字根相当于base是10的字符串哈希（把整个处理出来，把前面*权值后删掉），只不过这个哈希值就是这一段值的大小，就可以用这个哈希值预处理出(l,r)范围内的数字根的大小

%9 满足分配率，所有左边的未知数 x 和右边的未知数 y 的大小是[0,8] ，将所有以 L 为起点，长度为 w 的数字根 % 9 之后的值 k ,将当前的 a 装入 v[a] ，然后遍历所有的值，寻找满足条件的情况就可以了

当遇到满足条件的情况，如果它们 % k 的值a 相同 ，v[a]里面装的左端点数量要大于等于2才行，因为如果只有一个，就不满足 L1 != L2 。然后取 L1 和 L2字典序最小的答案就可以了。

//#define int ll
const int N = 2e5+10;
int n,m,w;
char s[N];
int p[N],val[N];

string str;

//处理 l 到 r 区间内的数字根的值 
int calc(int l,int r) {
    return ((s[r] - s[l-1] * p[r-l]) % 9 + 9) % 9;
} 

void solve()
{
//    cin>>n>>m;
    cin>>str;
    n = str.size();
    str = ' ' + str;
    cin>>w>>m;
    fo(i,1,n) {
        p[i] = p[i-1] * 10 % 9;
        s[i] = (s[i-1] * 10 + str[i] - '0') % 9;
    }
    vector<int> v[10];
    for(int l = 1,r = l + w - 1;r <= n;l ++ ,r ++ ) {
        //计算所有以 l 为起点长度是 w 的字符串的数字根 % 9 之后的值 
        val[l] = ((s[r] - s[l-1] * p[r-l]) % 9 + 9) % 9;
        //将它的左坐标存到数组里 
        v[val[l]].pb(l);
    }
    
    while(m -- ) {
        pii res = {inf,inf};
        int l,r,k;cin>>l>>r>>k;
        int t = calc(l,r);
        for(int i = 0;i <= 9;i ++ ) {
            if(v[i].empty()) continue;
            for(int j = 0;j <= 9;j ++ ) {
                if(v[j].empty()) continue;
                if((t * i + j) % 9 == k) {
                    if(i == j && v[i].size() > 1) res = min(res,{v[i][0],v[i][1]});
                    if(i != j) res = min(res, {v[i][0],v[j][0]});
                }
            }
        }
        if(res.first == inf) res = {-1,-1};
        cout<<res.first<<' '<<res.second<<endl;  
    }
}