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>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

struct RollingHash{
    static const int MD = 2;
    static const vector<ll> hash_base, hash_mod;

    int n;
    vector<ll> hs[MD], pw[MD];

    RollingHash(){}
    RollingHash(const string &s){
        n = s.size();
        rep(i,MD){
            hs[i].assign(n+1,0);
            pw[i].assign(n+1,0);
            hs[i][0] = 0;
            pw[i][0] = 1;
            rep(j,n){
                pw[i][j+1] = pw[i][j]*hash_base[i] % hash_mod[i];
                hs[i][j+1] = (hs[i][j]*hash_base[i]+s[j]) % hash_mod[i];
            }
        }
    }

    // 1-index
    ll hash_value(int l, int r, int i){
        return ((hs[i][r] - hs[i][l]*pw[i][r-l])%hash_mod[i]+hash_mod[i])%hash_mod[i];
    }

    bool match(int l1, int r1, int l2, int r2){
        bool ret = true;
        rep(i,MD) ret &= (hash_value(l1-1,r1,i) == hash_value(l2-1,r2,i));
        return ret;
    }

    vector<ll> calc(int l, int r){
        vector<ll> ret(MD);
        rep(i,MD) ret[i]=hash_value(l-1,r,i);
        return ret;
    }
};
const vector<ll> RollingHash::hash_base{1009,1021};
const vector<ll> RollingHash::hash_mod{1000000009,1000000007};

int main(){
    string s;
    int Q;
    cin >>s >>Q;
    int S = s.size();

    string rev = s;
    reverse(all(rev));

    RollingHash H(s),T(rev);

    while(Q--){
        int l,r,t;
        scanf(" %d %d %d", &l, &r, &t);

        vector<int> check;
        // prefix
        int L = l, R = r;
        int ok = L+t-1, ng = R+1;
        rep(i,2){
            // printf(" binary s %d %d \n",ok,ng);
            // dbg(L);
            while(ng-ok>1){
                int mid = (ok+ng)/2;
                if(H.match(L+t,mid,L,mid-t)) ok = mid;
                else ng = mid;
            }
            if(l<=ok+1 && ok+1<=r) check.pb(ok+1);
            // dbg(ok+1);
            L = ok+2-t;
            ok = L+t-1;
            ng = R+1;
        }

        // suffix
        int cv_l = S-r+1, cv_r = S-l+1;
        L = cv_l;
        R = cv_r;
        ok = L+t-1;
        ng = R+1;
        rep(i,2){
            // printf(" binary s %d %d \n",ok,ng);
            // dbg(L);
            while(ng-ok>1){
                int mid = (ok+ng)/2;
                if(T.match(L+t,mid,L,mid-t)) ok = mid;
                else ng = mid;
            }
            if(l<=S+1 - (ok+1) && S+1 - (ok+1)<=r) check.pb(S+1 - (ok+1));
            // dbg(ok+1);
            // dbg(S+1 - (ok+1));
            L = ok+2-t;
            ok = L+t-1;
            ng = R+1;
        }

        set<int> IDX;
        for(int i:check){
            for(int j=-1; j<=1; ++j){
                int idx = i + j*t;
                if(l<=idx && idx<=r) IDX.insert(idx);
            }
        }
        map<char,int> mm;
        for(int idx:IDX){
            // printf(" FOCUS :: %d %c\n",idx,s[idx-1]);
            ++mm[s[idx-1]];
        }

        bool ans = true;
        if(mm.size() > 2) ans = false;
        else if(mm.size() == 2){
            vector<int> v;
            for(const auto p:mm) v.pb(p.se);
            if(min(v[0],v[1])>1) ans = false;
        }

        printf("%s\n", (ans?"Yes":"No"));
    }
    return 0;
}