from collections import defaultdict
for ik in range(int(input())):
s=list(input())
n=len(s)
w,m=map(int,input().split())
arr=[0]
for q in range(n):
arr.append(arr[-1]*10+int(s[q]))
arr[-1]%=9
def calc(x,y):
num=arr[y]-arr[x-1]*pow(10,x,9)
return num%9
ind=defaultdict(list)
for i in range(1,n-w+2):
ind[calc(i,i+w-1)].append(i)
for i in range(m):
ans = (10 ** 9, 10 ** 9)
l,r,k=map(int,input().split())
q=calc(l,r)
for j in ind:
l1=ind[j][0]
req=(k-j*q)%9
if req==j:
if len(ind[j])>1:
l2=ind[j][1]
ans=min(ans,(l1,l2))
else:
if req in ind and len(ind[req])>0:
l2=ind[req][0]
ans=min(ans,(l1,l2))
if ans==(10**9,10**9):
print(-1,-1)
else:
print(ans[0],ans[1])#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
long long int n,q,w,i,j;
string s;
cin>>s;
cin>>w;
cin>>q;
n=s.size();
int a[n];
a[n-1]=s[n-1]-'0';
for(i=n-2;i>=0;i--){
a[i]=s[i]-'0'+a[i+1];
}
map< int,vector<pair< int, int> >>m;
for(i=0 ; i <= n-w ; i++)
{
int x;
if(i!=n-w) x=a[i]-a[i+w];
else x=a[i];
m[x%9].push_back(make_pair(i,x));
}
for(i=0 ; i < 9 ; i++)
{
sort(m[i].begin(),m[i].end());
}
while(q--){
int l,r,k;
cin>>l>>r>>k;
l--,r--;
int x=a[l],z,p=1000000000,ans,v;
if(r!=n-1)x=a[l]-a[r+1];
x=x%9;
for(i=0 ; i < 9 ; i++)
{
z=(27+k-(x*i)%9)%9;
if(z!=i && m[z].size()>0 && m[i].size()>0){
v=m[i][0].first;
p=min(p,v);
if(p==v)ans=i;
}
else if(z==i && m[i].size()>1){
v=m[i][0].first;
p=min(v,p);
if(p==v)ans=i;
}
}
if(p==1000000000)cout<<-1<<" "<<-1<<endl;
else{
// cout<<1<<endl;
z=(27+k-(x*ans)%9)%9;
if(z==ans)cout<<m[ans][0].first+1<<" "<<m[ans][1].first+1<<endl;
else cout<<m[ans][0].first+1<<" "<<m[z][0].first+1<<endl;
}
}
}
} 734A - Anton and Danik | 1300B - Assigning to Classes |
1647A - Madoka and Math Dad | 710A - King Moves |
1131A - Sea Battle | 118A - String Task |
236A - Boy or Girl | 271A - Beautiful Year |
520B - Two Buttons | 231A - Team |
479C - Exams | 1030A - In Search of an Easy Problem |
158A - Next Round | 71A - Way Too Long Words |
160A - Twins | 1A - Theatre Square |
1614B - Divan and a New Project | 791A - Bear and Big Brother |
1452A - Robot Program | 344A - Magnets |
96A - Football | 702B - Powers of Two |
1036A - Function Height | 443A - Anton and Letters |
1478B - Nezzar and Lucky Number | 228A - Is your horseshoe on the other hoof |
122A - Lucky Division | 1611C - Polycarp Recovers the Permutation |
432A - Choosing Teams | 758A - Holiday Of Equality |