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;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int NN,k;
int ran[100005];
int tmp[100005];
int sa[100005];

bool compare_sa(int i,int j)
{
	if(ran[i] != ran[j]) return ran[i] < ran[j];
	else
	{
		int ri = i+k<=NN ? ran[i+k]: -1;
		int rj = j+k<=NN ? ran[j+k]: -1;
		
		return ri < rj;
	}
}

void construct_sa(string S)
{
	NN = S.size();
	for(int i=0;i<=NN;i++)
	{
		sa[i] = i;
		ran[i] = i<NN?S[i]:-1;
	}
	
	for(k=1;k<=NN;k*=2)
	{
		sort(sa,sa+NN+1,compare_sa);
		
		tmp[sa[0]] = 0;
		for(int i=1;i<=NN;i++)
		{
			tmp[sa[i]] = tmp[sa[i-1]] + compare_sa(sa[i-1],sa[i]);
		}
		for(int i=0;i<=NN;i++)
		{
			ran[i] = tmp[i];
		}
	}
}
int lcp[100005];
void construct_lcp(string S)
{
	int n = S.size();
	for(int i=0;i<=n;i++) ran[sa[i]] = i;
	
	int h = 0;
	lcp[0] = 0;
	
	for(int i=0;i<n;i++)
	{
		int j = sa[ran[i]-1];
		
		if(h) h--;
		for(;j+h<n && i+h<n;h++)
		{
			if(S[j+h] != S[i+h]) break;
		}
		lcp[ran[i]-1] = h;
	}
}

int seg[(1<<18)+5];
void update(int k,int a){
	k+=(1<<17)-1; seg[k] = a;
	while(k>0){
		k=(k-1)/2;
		seg[k]=min(seg[k*2+1],seg[k*2+2]);
	}
}
int query(int a,int b,int k,int l,int r){
	if(r<a || b<l) return INF;
	if(a<=l && r<=b) return seg[k];
	else{
		int vl=query(a,b,k*2+1,l,(l+r)/2);
		int vr=query(a,b,k*2+2,(l+r)/2+1,r);
		return min(vl,vr);
	}
}
string s;
int main(){
	cin >> s;
	construct_sa(s);
	construct_lcp(s);
	for(int i=0;i<s.size();i++){
		update(i,lcp[i]);
	}
	int q; cin >> q;
	for(int i=0;i<q;i++){
		int L,R,T; cin >> L >> R >> T;
		if(R-L+1 <= T){
			puts("Yes"); continue;
		}
		int P = ran[L-1];
		int Q = ran[L+T-1];
		int len = query(min(P,Q),max(P,Q)-1,0,0,(1<<17)-1); //cout << len << endl;
		if(len >= R-L+1-T){
			puts("Yes");
		}
		else{
			P = ran[L-1+len+1];
			Q = ran[L+T-1+len+1];
			int len2 = query(min(P,Q),max(P,Q)-1,0,0,(1<<17)-1);//cout << len << endl;
			int D = (T-1-len%T); D = min(D,R-L-T-len);//cout << D ;
			if(len2<D) puts("No");
			else{
				if(D != T-1-len%T) puts("Yes");
				else{
					if(L-1+T+T+len+D+1 <= R){
						P = ran[L-1+T+len+D+1]; 
						Q = ran[L-1+T+T+len+D+1];
						int len3 = query(min(P,Q),max(P,Q)-1,0,0,(1<<17)-1);
						if(len3 < R-L-T-T-len-D){
							puts("No"); continue;
						}
					}
					P = ran[L-1];
					Q = ran[L-1+T+len+D+1];
					int len4 = query(min(P,Q),max(P,Q)-1,0,0,(1<<17)-1);
					int E = min(T,R-L-T-len-D);
					P = ran[L-1+len+D+1];
					Q = ran[L-1+T+len+D+1];
					int len5 = query(min(P,Q),max(P,Q)-1,0,0,(1<<17)-1);
					int F = min(T,R-L-T-len-D);
					puts((len4 >= E)||(len5 >= F)?"Yes":"No");
				}
			}
		}
	}
}