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:
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2711"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#endif
//BEGIN CUT HERE
struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct SuffixArray{
  string s;
  vector<int> sa,rev;

  SuffixArray(){}
  SuffixArray(const string &S):s(S){
    int n=s.size();
    s.push_back('$');
    sa.resize(n+1);
    iota(sa.begin(),sa.end(),0);
    sort(sa.begin(),sa.end(),
         [&](int a,int b){
           if(s[a]==s[b]) return a>b;
           return s[a]<s[b];
         });
    vector<int> cs(n+1,0),rs(n+1),cnt(n+1);
    for(int i=0;i<=n;i++) rs[i]=s[i];
    for(int len=1;len<=n;len*=2){
      for(int i=0;i<=n;i++){
        cs[sa[i]]=i;
        if(i>0 &&
           rs[sa[i-1]]==rs[sa[i]] &&
           sa[i-1]+len<=n &&
           rs[sa[i-1]+len/2]==rs[sa[i]+len/2]) cs[sa[i]]=cs[sa[i-1]];
      }
      iota(cnt.begin(),cnt.end(),0);
      copy(sa.begin(),sa.end(),rs.begin());
      for(int i=0;i<=n;i++){
        int s1=rs[i]-len;
        if(s1>=0) sa[cnt[cs[s1]]++]=s1;
      }
      cs.swap(rs);
    }
    rev.resize(n+1);
    for(int i=0;i<=n;i++) rev[sa[i]]=i;
  }
  int operator[](int i) const{return sa[i];}

  bool lt_substr(string &t,int si,int ti){
    int sn=s.size(),tn=t.size();
    while(si<sn&&ti<tn){
      if(s[si]<t[ti]) return 1;
      if(s[si]>t[ti]) return 0;
      si++;ti++;
    }
    return si==sn&&ti<tn;
  }

  int lower_bound(string& t){
    int l=0,r=s.size();
    while(l+1<r){
      int m=(l+r)>>1;
      if(lt_substr(t,sa[m],0)) l=m;
      else r=m;
    }
    return r;
  }

  int upper_bound(string& t){
    t.back()++;
    int res=lower_bound(t);
    t.back()--;
    return res;
  }

  // O(|T|*log|S|)
  int count(string& T){
    return upper_bound(T)-lower_bound(T);
  }
};
//END CUT HERE

#ifndef call_from_test
//INSERT ABOVE HERE
signed JOI2009HO_A(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n,m;
  string s;
  cin>>n>>m>>s;
  SuffixArray sa(s);
  string t="I";
  for(int i=0;i<n;i++) t+="OI";
  cout<<sa.count(t)<<endl;
  return 0;
}
/*
  verified on 2019/10/28
  https://atcoder.jp/contests/joi2009ho/tasks/joi2009ho_a
*/

signed main(){
  JOI2009HO_A();
  return 0;
};
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "suffixarray.cpp"
#undef call_from_test

#endif
//BEGIN CUT HERE
struct LongestCommonPrefix{
  SuffixArray sa;

  vector<int> ht;
  vector< vector<int> > dat;
  LongestCommonPrefix(string &s):sa(s){
    int n=s.size();
    vector<int> lcp(n,0);

    int t=0;
    lcp[0]=0;
    for(int i=0;i<n;i++){
      int j=sa[sa.rev[i]-1];
      if(t>0) t--;
      for(;j+t<n&&i+t<n;t++){
        if(sa.s[j+t]!=sa.s[i+t]) break;
      }
      lcp[sa.rev[i]-1]=t;
    }

    int h=1;
    while((1<<h)<n) h++;
    dat.assign(h,vector<int>(n));
    ht.assign(n+1,0);
    for(int j=2;j<=n;j++) ht[j]=ht[j>>1]+1;

    for(int j=0;j<n;j++) dat[0][j]=lcp[j];
    for(int i=1,p=1;i<h;i++,p<<=1)
      for(int j=0;j<n;j++)
        dat[i][j]=min(dat[i-1][j],dat[i-1][min(j+p,n-1)]);
  }

  // a, b are indices for suffix array
  int query(int a,int b){
    assert(a!=b);
    if(a>b) swap(a,b);
    int l=b-a;
    return min(dat[ht[l]][a],dat[ht[l]][b-(1<<ht[l])]);
  }

  // a, b are indices for string
  int lcp(int a,int b){
    return query(sa.rev[a],sa.rev[b]);
  }
};
//END CUT HERE
#ifndef call_from_test

#define call_from_test
#include "../tools/fastio.cpp"
#include "../tools/chminmax.cpp"
#undef call_from_test

//INSERT ABOVE HERE
signed ARC060_F(){
  string s;
  cin>>s;
  int n=s.size();
  {
    string t(s);
    t.erase(unique(t.begin(),t.end()),t.end());
    if(t.size()==1u){
      cout<<n<<endl<<1<<endl;
      return 0;
    }
  }

  vector<vector<int> > v(n+1);
  for(int i=1;i<=n;i++)
    for(int j=i+i;j<=n;j+=i)
      v[j].emplace_back(i);

  LongestCommonPrefix lcp(s);
  auto check=
    [&](int l,int r)->int{
      for(int x:v[r-l])
        if(lcp.lcp(l,l+x)>=r-l-x) return 0;
      return 1;
    };

  if(check(0,n)){
    cout<<1<<endl<<1<<endl;
    return 0;
  }

  int ans=0;
  for(int i=1;i<n;i++)
    ans+=check(0,i)&&check(i,n);

  cout<<2<<endl<<ans<<endl;
  return 0;
}
/*
  verified on 2019/10/25
  https://atcoder.jp/contests/arc060/tasks/arc060_d
*/

signed main(){
  ARC060_F();
  return 0;
};
#endif

#undef call_from_test

signed main(){
  string s;
  cin>>s;
  LongestCommonPrefix lcp(s);
  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int l,r,t;
    cin>>l>>r>>t;
    l--;
    int x=lcp.lcp(l,l+t);
    if(l+t+x+1>=r){
      cout<<"Yes\n";
      continue;
    }
    int y=lcp.lcp(l+x+1,l+t+x+1);
    if(l+t+x+1+y>=r){
      cout<<"Yes\n";
      continue;
    }
    if(l+x+1+y<l+t){
      cout<<"No\n";
      continue;
    }
    int z=lcp.lcp(l+x+1+y+1,l+t+x+1+y+1);
    //cout<<x<<" "<<y<<" "<<z<<endl;
    if(l+t+x+1+y+1+z<r){
      cout<<"No\n";
      continue;
    }
    if(x+t==x+1+y&&s[l+x]==s[l+x+t+t]) cout<<"Yes\n";
    else cout<<"No\n";
  }
  cout<<flush;
  return 0;
}