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;
using P = pair<ll, ll>;
const ll mod = 1e9 + 7;
const ll b1 = 9973, b2 = 100000007;

ll Pow(ll a, ll b) {
	ll res = 1; a %= mod;
	while (b) {
		if (b & 1) {
			res = (res * a) % mod;
		}
		a = (a * a) % mod;
		b >>= 1;
	}
	return res;
}

class RollingHash {
	int N;
	string s;
	vector<ll> r1, r2, h1, h2, rh1, rh2;
public:
	RollingHash(const string& s_)
		: N((int)s_.size()), s(s_), r1(N + 1), r2(N + 1), h1(N + 1), h2(N + 1), rh1(N + 1), rh2(N + 1) {
		r1[0] = r2[0] = 1;
		for (int i = 1; i <= N; i++) r1[i] = r1[i - 1] * b1 % mod;
		for (int i = 1; i <= N; i++) r2[i] = r2[i - 1] * b2 % mod;

		h1[0] = h2[0] = 1;
		for (int i = 1; i <= N; i++) h1[i] = (h1[i - 1] * b1 + s[i - 1]) % mod;
		for (int i = 1; i <= N; i++) h2[i] = (h2[i - 1] * b2 + s[i - 1]) % mod;
	}
	P get(int l, int r) {
		return P((h1[r + 1] - h1[l] * r1[r - l + 1] % mod + mod) % mod, (h2[r + 1] - h2[l] * r2[r - l + 1] % mod + mod) % mod);
	}
};

int main()
{
	cin.sync_with_stdio(false);
	int Q;
	string S;
	cin >> S >> Q;
	int N = S.size();
	RollingHash rh(S);
	vector<P> dis;
	for (int i = 0; i < N; i++) {
		for (int j = -25; j <= 25; j++) {
			dis.push_back(P(Pow(b1, i) * (mod + j) % mod, Pow(b2, i) * (mod + j) % mod));
		}
	}
	sort(dis.begin(), dis.end());
	for (int i = 0, l, r, t; i < Q; i++) {
		cin >> l >> r >> t; l--; r--;
		auto lrh = rh.get(l, r - t), rrh = rh.get(l + t, r);
		ll d1 = (lrh.first - rrh.first + mod) % mod, d2 = (lrh.second - rrh.second + mod) % mod;
		if (r - l + 1 > t * 2) {
			if (binary_search(dis.begin(), dis.end(), P(d1, d2))) {
				puts("Yes");
			}
			else {
				int w = r - l + 1 , fl = (r - l + 1) / t * t;
				if (w == fl && rh.get(l, l + t - 1) != rh.get(r - t + 1, r)) {
					puts("No");
					continue;
				}
				if (w != fl && (rh.get(l, l + w - fl - 1) != rh.get(r - (w - fl - 1), r) || rh.get(l + w - fl, l + t - 1) != rh.get(r - t + 1, r - (w - fl)))) {
					puts("No");
					continue;
				}
				ll lb = t - 1, ub = r - l + 1 - t;
				while (lb + 1 < ub) {
					ll c = (lb + ub) / 2;
					lrh = rh.get(l, l + c - 1), rrh = rh.get(l + t, l + t + c - 1);
					d1 = (lrh.first - rrh.first + mod) % mod, d2 = (lrh.second - rrh.second + mod) % mod;
					if (binary_search(dis.begin(), dis.end(), P(d1, d2))) {
						lb = c;
					}
					else {
						ub = c;
					}
				}
				ll tmp = lb;
				lb = t - 1, ub = r - l + 1 - t;
				while (lb + 1 < ub) {
					ll c = (lb + ub) / 2;
					lrh = rh.get(r - t - c + 1, r - t), rrh = rh.get(r - c + 1, r);
					d1 = (lrh.first - rrh.first + mod) % mod, d2 = (lrh.second - rrh.second + mod) % mod;
					if (binary_search(dis.begin(), dis.end(), P(d1, d2))) {
						lb = c;
					}
					else {
						ub = c;
					}
				}
				puts(tmp + lb == r - l || lb == r - l + 1 - t ? "Yes" : "No");
			}
		}
		else {
			puts(binary_search(dis.begin(), dis.end(), P(d1, d2)) ? "Yes" : "No");
		}
	}
	return 0;
}