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 <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
template<class type>
class string_hash {
protected:
	std::vector<type> pw;
	std::vector<type> prefix;
	std::string s;
public:
	static const type base = type(311);
	string_hash() : s(), pw(type(1)), prefix(type(0)) {};
	string_hash(std::string s_) : s(s_) {
		pw.resize(s.length() + 1);
		prefix.resize(s.length() + 1);
		pw[0] = type(1);
		prefix[0] = type(0);
		for (size_t i = 0; i < s.length(); ++i) {
			pw[i + 1] = pw[i] * base;
			prefix[i + 1] = prefix[i] * base + type(s[i]);
		}
	};
	type get() { return s; }
	type get_hash(size_t l, size_t r) {
		return prefix[r] - pw[r - l] * prefix[l];
	}
};
template<class hash_type>
class string_diff01 : public string_hash<hash_type> {
public:
	string_diff01() : string_hash<hash_type>() {};
	string_diff01(std::string s_) : string_hash<hash_type>(s_) {};
	bool diff0(size_t la, size_t lb, size_t d) {
		// Judges that s[la, la + d) and s[lb, lb + d) are the same
		return string_hash<hash_type>::get_hash(la, la + d) == string_hash<hash_type>::get_hash(lb, lb + d);
	}
	bool diff1(size_t la, size_t lb, size_t d) {
		// Judges that s[la, la + d) and s[lb, lb + d) differs at most single character
		size_t pl = 0, pr = d + 1;
		while (pr - pl > 1) {
			size_t pm = (pl + pr) >> 1;
			if (string_hash<hash_type>::get_hash(la, la + pm) == string_hash<hash_type>::get_hash(lb, lb + pm)) {
				pl = pm;
			}
			else {
				pr = pm;
			}
		}
		if (pl == d) return true;
		return string_hash<hash_type>::get_hash(la + pr, la + d) == string_hash<hash_type>::get_hash(lb + pr, lb + d);
	}
};
using namespace std;
int main() {
	using hash_type = unsigned long long;
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	string S; int Q;
	cin >> S >> Q;
	string_diff01<hash_type> H(S);
	function<bool(int, int, int)> is_cyclic = [&](int L, int R, int T) {
		// Supposing that (R - L) is divisible by T
		int num_cycle = (R - L) / T;
		while (num_cycle > 1) {
			if (num_cycle & 1) {
				--num_cycle;
				if (!H.diff0(L, L + num_cycle * T, T)) return false;
			}
			else {
				num_cycle >>= 1;
				if (!H.diff0(L, L + num_cycle * T, num_cycle * T)) return false;
			}
		}
		return true;
	};
	function<bool(int, int, int)> solve = [&](int L, int R, int T) {
		int num_cycle = (R - L) / T;
		int remains = (R - L) % T;
		if (num_cycle == 0) return true;
		if (num_cycle == 1) return H.diff1(L, L + T, remains);
		if (num_cycle == 2) {
			if (!H.diff1(L, L + T, T)) return false;
			if (H.diff0(L, L + T, T)) return H.diff1(L, L + 2 * T, remains);
			if (H.diff0(L, L + T, remains)) return H.diff0(L, L + 2 * T, remains);
			return H.diff0(L, L + 2 * T, remains) || H.diff0(L + T, L + 2 * T, remains);
		}
		const vector<int> divs = { -1, -1, -1, 3, 4, 5, 3, 3, 4 };
		int div = (num_cycle >= 9 ? 3 : divs[num_cycle]), largeT = (num_cycle / div) * T;
		vector<hash_type> h(div);
		for (int i = 0; i < div; ++i) {
			h[i] = H.get_hash(L + i * largeT, L + (i + 1) * largeT);
		}
		vector<hash_type> h_sorted = h;
		sort(h_sorted.begin(), h_sorted.end());
		int sep = -1, sepcnt = 0;
		for (int i = 1; i < div; ++i) {
			if (h_sorted[i] != h_sorted[i - 1]) {
				sep = i;
				++sepcnt;
			}
		}
		if (sepcnt >= 2 || (1 < sep && sep < div - 1)) return false;
		hash_type truth = (sep != 1 ? h_sorted[0] : h_sorted[1]);
		int truth_pos = -1, wrong_pos = -1;
		for (int i = div - 1; i >= 0; --i) {
			if (h[i] == truth) truth_pos = i;
			else wrong_pos = i;
		}
		if (!is_cyclic(L + truth_pos * largeT, L + (truth_pos + 1) * largeT, T)) return false;
		if (sep == -1) return H.diff1(L, L + div * largeT, R - L - div * largeT);
		if (!H.diff1(L + truth_pos * largeT, L + wrong_pos * largeT, largeT)) return false;
		return H.diff0(L + truth_pos * largeT, L + div * largeT, R - L - div * largeT);
	};
	for (int i = 0; i < Q; ++i) {
		int L, R, T;
		cin >> L >> R >> T; --L;
		bool ans = solve(L, R, T);
		cout << (ans ? "Yes\n" : "No\n");
	}
	return 0;
}