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;
#define Long __int128_t
#define int long long
#define REP(i, n) for (int i = 0; i < (n); i++)

Long modpow(Long a, Long n, Long mod) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        Long t = modpow(a, n / 2, mod);
        return t * t % mod;
    }
    return a * modpow(a, n - 1, mod) % mod;
}

Long modinv(Long a, Long mod) { return modpow(a, mod - 2, mod); }

map<Long, Long> memo[101010];

// a^0 + a^1 + ... + a^{n-1}
Long powsum(Long a, Long n, Long mod) {
    if (memo[n].count(a)) return memo[n][a];
    if (n == 0) return 0;
    if (n % 2 == 0) {
        Long t = powsum(a, n / 2, mod);
        return memo[n][a] = (1 + modpow(a, n / 2, mod)) * t % mod;
    }
    return memo[n][a] = (modpow(a, n - 1, mod) + powsum(a, n - 1, mod)) % mod;
}

template <Long mod, Long p = 257>
struct RollingHash {
    int n;
    vector<Long> table;
    vector<Long> pows;
    RollingHash(const string &s) : n(s.size()), table(n + 1), pows(n + 1) {
        table[0] = 1;
        pows[0] = 1;
        for (int i = 0; i < n; i++) {
            table[i + 1] = (table[i] * p + s[i]) % mod;
            pows[i + 1] = pows[i] * p % mod;
        }
    }

    // [l, r)
    Long hash_substr(int l, int r) {
        Long ret = (table[r] - table[l] * pows[r - l]) % mod;
        if (ret < 0) ret += mod;
        return ret;
    }

    // [sl, sr)が[tl, tr) + [tl2, tr2)を繰り返したものになっているか
    bool is_periodic(int sl, int sr, int tl, int tr, int tl2 = 0, int tr2 = 0) {
        int slen = sr - sl, tlen = tr - tl, tlen2 = tr2 - tl2;
        int k = slen / (tlen + tlen2);
        Long target = (hash_substr(tl, tr) * pows[tlen2] % mod + hash_substr(tl2, tr2)) *
                      powsum(pows[tlen + tlen2], k, mod) % mod;
        int need = slen % (tlen + tlen2);
        target = target * pows[need] % mod;
        if (need <= tlen) {
            target += hash_substr(tl, tl + need);
        } else {
            need -= tlen;
            Long add = hash_substr(tl, tr);
            add = add * pows[need] % mod;
            add += hash_substr(tl2, tl2 + need);
            target += add;
        }
        target %= mod;
        return target == hash_substr(sl, sr);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;

    RollingHash<4611686018427387903> rh(s);

    auto hoge = [&](int l, int r, int t) {
        int len = r - l;
        int L = 0, R = len;
        while (L < R - 1) {
            int M = (L + R) / 2;
            if (rh.is_periodic(l, l + M, l, l + t)) {
                L = M;
            } else {
                R = M;
            }
        }
        int amari = (L + 1) % t;
        return rh.is_periodic(l + L + 1, r, l + amari, l + t, l, l + amari);
    };

    int q;
    cin >> q;
    while (q--) {
        int l, r, t;
        cin >> l >> r >> t;
        l--;
        if (rh.is_periodic(l, r, l, l + t)) {
            cout << "Yes" << '\n';
            continue;
        }

        if (hoge(l, r, t)) {
            cout << "Yes" << '\n';
            continue;
        }

        if (r - l < t * 2) {
            cout << "No" << '\n';
            continue;
        }

        if (!rh.is_periodic(l + t, r, l + t, l + t + t)) {
            cout << "No" << '\n';
            continue;
        }

        if (hoge(l, l + 2 * t, t)) {
            cout << "Yes" << '\n';
            continue;
        }

        cout << "No" << '\n';
    }
}