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>;
constexpr ll po(const ll p, const ll n, const ll mod)
{
    if (n == 0) { return 1; }
    if (n % 2 == 1) {
        return po(p, n - 1, mod) * p % mod;
    } else {
        const ll pp = po(p, n / 2, mod);
        return pp * pp % mod;
    }
}
constexpr ll inv(const ll p, const ll mod) { return po(p, mod - 2, mod); }
constexpr ll BASE1 = 186398169LL;
constexpr ll MOD1 = 1000000007LL;
constexpr ll INV1 = inv(BASE1, MOD1);
constexpr ll BASE2 = 238173201LL;
constexpr ll MOD2 = 1000000009LL;
constexpr ll INV2 = inv(BASE2, MOD2);
constexpr int MAX = 100000;
P power[MAX], inverse[MAX], h[MAX];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    for (ll i = 0, p1 = 1, p2 = 1, i1 = 1, i2 = 1, h1 = 0, h2 = 0; i < S.size(); i++, (p1 *= BASE1) %= MOD1, (p2 *= BASE2) %= MOD2, (i1 *= INV1) %= MOD1, (i2 *= INV2) %= MOD2) { (h1 += (S[i] - 'a') * p1 % MOD1) %= MOD1, (h2 += (S[i] - 'a') * p2 % MOD2) %= MOD2, h[i] = {h1, h2}, inverse[i] = {i1, i2}, power[i] = {p1, p2}; };
    auto add = [](const P& p1, const P& p2) -> P { return {(p1.first + p2.first) % MOD1, (p1.second + p2.second) % MOD2}; };
    auto sub = [](const P& p1, const P& p2) -> P { return {(p1.first + MOD1 - p2.first) % MOD1, (p1.second + MOD2 - p2.second) % MOD2}; };
    auto mul = [](const P& p1, const P& p2) -> P { return {(p1.first * p2.first) % MOD1, (p1.second * p2.second) % MOD2}; };
    auto getHash = [&](const int s, const int l) -> P { return l == 0 ? P{0, 0} : s == 0 ? h[s + l - 1] : mul(sub(h[s + l - 1], h[s - 1]), inverse[s]); };
    int Q;
    cin >> Q;
    for (int q = 0; q < Q; q++) {
        int l, r, t;
        (cin >> l >> r >> t), l--;
        const int L = r - l;
        int inf = 0, sup = L - t;
        while (sup - inf > 1) {
            const int mid = (inf + sup) / 2;
            if (getHash(l, mid) == getHash(l + t, mid)) {
                inf = mid;
            } else {
                sup = mid;
            }
        }
        bool ok = false;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 2; j++) {
                const int pos = j == 0 ? inf : inf + t;
                const P ch = sub({i, i}, {S[pos + l] - 'a', S[pos + l] - 'a'});
                const P off1 = (pos < L - t ? power[pos] : P{0, 0});
                const P off2 = (pos >= t ? power[pos - t] : P{0, 0});
                if (add(getHash(l, L - t), mul(off1, ch)) == add(getHash(l + t, L - t), mul(off2, ch))) {
                    ok = true;
                    break;
                }
            }
        }
        cout << (ok ? "Yes\n" : "No\n");
    }
}