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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-12;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
class seg{
public:
	vector<int>val;
	seg(void){val.res(262144);
		for(int i=0;i<262144;i++){val[i]=mod;}
	}
	int ask(int hda,int mgi){
		hda+=131072;
		mgi+=131072;
		int ans=mod;
		while(hda+1<mgi){
			if(hda%2==0){mineq(ans,val[hda+1]);}
			if(mgi%2==1){mineq(ans,val[mgi-1]);}
			hda/=2;mgi/=2;
		}
		return ans;
	}
	void cha(int bas,int num){
		bas+=131072;
		while(bas>1){
			mineq(val[bas],num);
			bas/=2;
		}
	}
};
struct SuffixArray{
	vector<int> SA;
	vector<int>GYA;//SAの逆
	vector<int>LCP;
	seg ki;
	string s;
	void Build_SA(const string& str){
		s = str;
		SA.resize(s.size());
		iota(begin(SA), end(SA), 0);
		sort(begin(SA), end(SA), [&](const int& a, const int& b)
		{
			if(s[a] == s[b]) {return(a > b);}
			return (s[a] < s[b]);
		});
		vector< int > classes(s.size()), c(s.size()), cnt(s.size());
		for(int i = 0; i < s.size(); i++) {c[i] = s[i];}
		for(int len = 1; len < s.size(); len <<= 1) {
			for(int i = 0; i < s.size(); i++) {
				if(i > 0 && c[SA[i - 1]] == c[SA[i]] && SA[i - 1] + len < s.size() && c[SA[i - 1] + len / 2] == c[SA[i] + len / 2]) {
					classes[SA[i]] = classes[SA[i - 1]];
				} else {
					classes[SA[i]] = i;
				}
			}
			iota(begin(cnt), end(cnt), 0);
			copy(begin(SA), end(SA), begin(c));
			for(int i = 0; i < s.size(); i++) {
				int s1 = c[i] - len;
				if(s1 >= 0) SA[cnt[classes[s1]]++] = s1;
			}
			classes.swap(c);
		}
		int ss=s.size();
		SA.insert(SA.begin(),ss);
	}
	int operator[](int k) const{return (SA[k]);}
	int size() const{return (s.size()+1);}
	bool lt_substr(string& t, int si = 0, int ti = 0)
	{
		int sn = s.size(), tn = t.size();
		while(si < sn && ti < tn) {
			if(s[si] < t[ti]) return (true);
			if(s[si] > t[ti]) return (false);
			++si, ++ti;
		}
		return (si >= sn && ti < tn);
	}
	int lower_bound(string& t)
	{
		int low = -1, high = SA.size();
		while(high - low > 1) {
			int mid = (low + high) >> 1;
			if(lt_substr(t, SA[mid])) low = mid;
			else high = mid;
		}
		return (high);
	}
	pair< int, int > lower_upper_bound(string& t)
	{
		int idx = lower_bound(t);
		int low = idx - 1, high = SA.size();
		t.back()++;
		while(high - low > 1) {
			int mid = (low + high) >> 1;
			if(lt_substr(t, SA[mid])) low = mid;
			else high = mid;
		}
		t.back()--;
		return (make_pair(idx, high));
	}
	void output()
	{
		for(int i = 0; i < size(); i++) {
			cout << i << ": " << s.substr(SA[i]) <<" "<<LCP[i]<< endl;
		}
	}
	void Build_LCP(void){
		GYA.resize(s.size()+1);
		LCP.resize(s.size()+1);
		int n=s.size(),i;
		for(i=0;i<=n;i++){GYA[SA[i]]=i;}
		int h=0;LCP[0]=0;
		for(i=0;i<n;i++){
			int j=SA[GYA[i]-1];
			if(h>0){h--;}
			for(;j+h<n&&i+h<n;h++){
				if(s[j+h]!=s[i+h]){break;}
			}
			LCP[GYA[i]-1]=h;
			ki.cha(GYA[i],h);
		}
	}
	int LCP_mozi(int l,int r){//何文字一致?
		l=GYA[l];r=GYA[r];
		if(l>r){swap(l,r);}
		return ki.ask(l,r+1);
	}
};
int main(void){
	cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);
	string s;cin>>s;s.pub('#');
	SuffixArray sa;
	sa.Build_SA(s);
	
	sa.Build_LCP();
	//sa.output();
	int Q;cin>>Q;
	while(Q--){
		int l,r,t,T;cin>>l>>r>>t;l--;
		T=t;
		while(T*2<r-l){T*=2;}
		int kai=0,hen=0;
		bool can=true;
		while(T>=t){
			//cerr<<"T="<<T<<endl;
			int iti=sa.LCP_mozi(l,l+T);
			//cerr<<"iti="<<iti<<endl;
			if(kai==0){
				if(iti<r-l-T){
					hen=1;
					int bas=l+iti;//当たった場所
					if(sa.LCP_mozi(bas+1,bas+1+T)+iti+1<r-l-T){can=false;break;}
					int aaa=(iti>=T/2?iti-T/2:iti+T/2);
					if(s[l+iti]!=s[l+aaa]){l=r-T;}
				}
			}
			else if(kai==1){
				if(iti<T){
					if(hen>0){can=false;break;}
					int bas=l+iti;//当たった場所
					if(sa.LCP_mozi(bas+1,bas+1+T)+iti+1<T){can=false;break;}//2回ダメ来た
					int zyu=r-l-T-T;//重複度
					int aaa=(iti>=T/2?iti-T/2:iti+T/2);
					//cerr<<"aaa="<<aaa<<endl;
					if(iti+T<zyu){can=false;break;}
					else if(iti>=zyu&&s[l+iti]!=s[l+aaa]){l+=T;}
				}
			}else{
				if(iti<T){can=false;break;}
			}
			kai++;T/=2;
		}
		cout<<(can?"Yes":"No")<<endl;
	}
	return 0;
}