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
#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];
map<P, int> phash;

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};
        for (int j = 1; j < 26; j++) { phash[{p1 * j % MOD1, p2 * j % MOD2}] = i; }
    };

    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]); };
    auto getSum = [&](const ll p, const ll n, const ll mod) -> ll { return p == 1 ? n : (po(p, n, mod) - 1) * inv(p - 1, mod) % mod; };
    auto getPoly = [&](const int t, const int rep) -> P { return {getSum(power[t].first, rep, MOD1), getSum(power[t].second, rep, MOD2)}; };
    auto judge = [&](const P& diff, const int L) -> bool { return diff == P{0, 0} or (phash.find(diff) != phash.end() and phash[diff] < L) or (phash.find(sub({0, 0}, diff)) != phash.end() and phash[sub({0, 0}, diff)] < L); };
    assert(phash.size() == 25 * S.size());
    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, rep = L / t, rest = L % t;
        const P Hash = getHash(l, L);
        if (rep == 1) {
            const P mask1 = add(getHash(l, t), mul(power[t * rep], getHash(l, rest)));
            const P diff = sub(mask1, Hash);
            cout << (judge(diff, L) ? "Yes\n" : "No\n");
        } else {
            const P poly = getPoly(t, rep);
            const P mask1 = add(mul(poly, getHash(l, t)), mul(power[t * rep], getHash(l, rest)));
            const P diff1 = sub(mask1, Hash);
            const P mask2 = add(mul(poly, getHash(l + t, t)), mul(power[t * rep], getHash(l + t, rest)));
            const P diff2 = sub(mask2, Hash);
            cout << (judge(diff1, L) or judge(diff2, L) ? "Yes\n" : "No\n");
        }
    }
}

