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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define SIZE 100005
#define NUM1 1000000007
#define NUM2 99999883

struct Info{
	ull hash_1,hash_2;
};

int T_length;
char T[SIZE];
ull HASH[SIZE][2],POW[SIZE][2];

bool IS_SAME(Info left,Info right){
	if(left.hash_1 == right.hash_1 && left.hash_2 == right.hash_2)return true;
	else{
		return false;
	}
}

Info calcHash(int left,int right){

	Info ret;

	int length = right-left+1;

	//indexのずれに注意:T[right]までのハッシュ値はHASH[right+1]に記録されている
	ret.hash_1 = HASH[right+1][0]-HASH[left][0]*POW[length][0];
	ret.hash_2 = HASH[right+1][1]-HASH[left][1]*POW[length][1];

	return ret;
}

//AとBの一致長さを返す
int calc_match_len(int start_A,int start_B,int length){

	int left = 0,right = length-1,mid = (left+right)/2;
	int match_len = 0;
	Info tmp_A,tmp_B;

	while(left <= right){

		tmp_A = calcHash(start_A,start_A+mid);
		tmp_B = calcHash(start_B,start_B+mid);

		if(IS_SAME(tmp_A,tmp_B)){
			match_len = mid+1;
			left = mid+1;
		}else{
			right = mid-1;
		}
		mid = (left+right)/2;
	}

	return match_len;
}

Info replace(Info X,int length,int loc,char pre,char next){

	X.hash_1 -= pre*POW[length-(loc+1)][0];
	X.hash_1 += next*POW[length-(loc+1)][0];

	X.hash_2 -= pre*POW[length-(loc+1)][1];
	X.hash_2 += next*POW[length-(loc+1)][1];

	return X;
}


int main(){

	scanf("%s",T);
	for(T_length = 0; T[T_length] != '\0'; T_length++);

	//2通りのハッシュ値を計算する
	HASH[0][0] = 0;
	HASH[0][1] = 0;
	POW[0][0] = 1;
	POW[0][1] = 1;

	//Tのハッシュ値を求める
	for(int i = 1; i <= T_length; i++){
		HASH[i][0] = T[i-1] + HASH[i-1][0]*NUM1;
		HASH[i][1] = T[i-1] + HASH[i-1][1]*NUM2;

		POW[i][0] = POW[i-1][0]*NUM1;
		POW[i][1] = POW[i-1][1]*NUM2;
	}

	int num_query;
	scanf("%d",&num_query);

	int left,right,cycle,length,match_len;
	Info A,B,replace_A,replace_B;

	Info debug;

	for(int loop = 0; loop < num_query; loop++){

		scanf("%d %d %d",&left,&right,&cycle);
		left--;
		right--;

		length = right-left+1;

		if(cycle == length){
			printf("Yes\n");
			continue;
		}

		A = calcHash(left,(left+length-1)-cycle);
		B = calcHash(left+cycle,right);

		if(IS_SAME(A,B)){
			printf("Yes\n");
			continue;
		}

		length = right-(left+cycle)+1; //★★長さを比較長に変更する★★

		match_len = calc_match_len(left,left+cycle,length);

		debug = calcHash(left,left+match_len-1);

		if(left+cycle+match_len <= left+length-1){ //★★不一致文字が、共通文字の場合

			//共通不一致文字をAの方に変える
			replace_A = replace(A,length,cycle+match_len,T[left+cycle+match_len],T[left+match_len]);
			replace_B = replace(B,length,match_len,T[left+cycle+match_len],T[left+match_len]);

			if(IS_SAME(replace_A,replace_B)){
				printf("Yes\n");
				continue;
			}

			replace_A = replace(A,length,match_len,T[left+match_len],T[left+cycle+match_len]);

			if(IS_SAME(replace_A,B)){
				printf("Yes\n");
			}else{
				printf("No\n");
			}

		}else{

			//不一致だった箇所を変更
			replace_A = replace(A,length,match_len,T[left+match_len],T[left+cycle+match_len]);
			replace_B = replace(B,length,match_len,T[left+cycle+match_len],T[left+match_len]);

			if(IS_SAME(replace_A,B) == true || IS_SAME(A,replace_B) == true){
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}
	}

	return 0;
}