Problem: Almost periodic string

Given the string S. Answer Q queries for this string S. In the i-th query, determine if S [l_i, \ r_i] can be a string of period t_i when you can change from S [l_i, \ r_i] to one character. S [l, \ r] represents the substring of the string S from the lth to the rth.

If the character string W is a character string with period t, then for i \ = \ 1, \ 2, \ ..., \ | W | − t, W_ {i} = W_ {i + t}. I will do it.

Constraints

* 1 ≤ | S | ≤ 10 ^ 5
* 1 ≤ Q ≤ 10 ^ 5
* 1 ≤ l_i ≤ r_i ≤ | S |
* 1 ≤ t_i ≤ r_i − l_i + 1
* S consists of only lowercase letters



Input Format

Input is given from standard input in the following format.


S
Q
l_1 r_1 t_1
...
l_Q r_Q t_Q


Output Format

Output over Q lines. On line i, print the answer to the i-th query with `Yes` or` No`.

Sample Input 1


abcabcaxcabc
Four
1 9 3
8 12 3
1 4 2
2 3 2


Sample Output 1


Yes
Yes
No
Yes


Sample Input 2


isuruu
Four
3 6 1
3 6 2
3 6 3
2 4 1


Sample Output 2


Yes
Yes
Yes
No






Example

Input

abcabcaxcabc
4
1 9 3
8 12 3
1 4 2
2 3 2


Output

Yes
Yes
No
Yes

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
// #include"../RollingHash.cpp"
#include<bits/stdc++.h>

namespace ProconLib{
    using Hash=__int128;
    
    template<typename Iter>
    class RollingHash{
        int N;
        const static Hash MOD=Hash(1e18l)+9;
        const static Hash A=Hash(1e12l)+39;
        std::vector<Hash> powA;
        std::vector<Hash> h;
        public:
        // RollingHash():N(xs.size()),powA(N+1),h(N+1){
        //     for(int i=0;i<N;i++) h[i+1]=(h[i]*A+xs[i])%MOD;
        //     powA[0]=1;
        //     for(int i=0;i+1<N;i++) powA[i+1]=(powA[i]*A)%MOD;
        // }
        RollingHash(Iter begin,Iter end):N(0),h(1,0){
            for(;begin!=end;begin++){
                h.push_back((h[N]*A+(*begin))%MOD);
                N++;
            }
            powA.resize(N+1);
            powA[0]=1;
            for(int i=0;i+1<=N;i++) powA[i+1]=(powA[i]*A)%MOD;
        }
        Hash get(int l,int r){
            return (h[r]+(MOD-(h[l]*powA[r-l])%MOD))%MOD;
        }
        Hash getA(){return A;}
        Hash getMOD(){return MOD;}
    };

    
};

using namespace std;
using namespace ProconLib;
int main(){
    string s;
    cin>>s;
    int q;
    cin>>q;
    RollingHash<string::iterator> rh(s.begin(),s.end());
    const Hash MOD=rh.getMOD();
    const Hash A=rh.getA();
    vector<Hash> powA(2*1e6);
    powA[0]=1;
    for(int i=0;i+1<powA.size();i++){
        powA[i+1]=powA[i]*A%MOD;
    }
    auto calc=[&](int l,int r,int l1,int r1,int l2,int r2,int t){
        Hash hv=(rh.get(l1,r1)*powA[r2-l2]+rh.get(l2,r2))%MOD;
        vector<Hash> rept(21);
        rept[0]=hv;
        for(int i=0;i<20;i++){
            if((1LL<<i)*t<=s.size()+1) rept[i+1]=(rept[i]*powA[(1LL<<i)*t]+rept[i])%MOD;
        }
        // cerr<<(long long)(rept[1])<<endl;
        // cerr<<(long long)(rh.get(0,6))<<endl;
        for(int i=20;i>=0;i--){
            long long ub=(1LL<<i)*t+l;
            if(ub>r) continue;
            Hash h=rh.get(l,ub);
            if(h==rept[i]){
                l=ub;
            }
        }
        int lb=l,ub=min(r,l+t)+1;
        while(ub-lb>1){
            int mid=(lb+ub)/2;
            int len=mid-l;
            Hash h=0;
            if(r1-l1<len){
                len=mid-l-(r1-l1);
                h=(rh.get(l1,r1)*powA[len]+rh.get(l2,l2+len))%MOD;
            }
            else{
                h=rh.get(l1,l1+len);
            }
            if(rh.get(l,mid)==h) lb=mid;
            else ub=mid;
        }
        return lb;
    };
    while(q--){
        int l,r,t;
        cin>>l>>r>>t;
        l--;
        int x=calc(l,r,l,l+t,l,l,t);
        x++;
        x=calc(x,r,(x-l)%t+l,l+t,l,(x-l)%t+l,t);
        int y=-1;
        if(l+2*t<=s.size()){
            y=calc(l,r,l+t,l+2*t,l,l,t);
            y++;
            y=calc(y,r,(y-l)%t+l+t,l+2*t,l+t,(y-l)%t+l+t,t);
        }
        cout<<((x>=r || y>=r) ? "Yes" : "No")<<endl;
    }

    return 0;    
}