Problem: You are developing a robot that processes strings. When the robot is given a string t consisting of lowercase English letters, it processes the string by following the procedure below:

1. Let i be the smallest index such that t_i = t_{i + 1}. If such an index does not exist, terminate the procedure.
2. If t_i is `z`, remove t_i and t_{i + 1} from t. Otherwise, let c be the next letter of t_i in the English alphabet, and replace t_i and t_{i + 1} together with c, reducing the length of t by 1.
3. Go back to step 1.



For example, when the robot is given the string `axxxxza`, it will be processed as follows: `axxxxza` → `ayxxza` → `ayyza` → `azza` → `aa` → `b`.

You are given a string s consisting of lowercase English letters. Answer Q queries. The i-th query is as follows:

* Assume that the robot is given a substring of s that runs from the l_i-th character and up to the r_i-th character (inclusive). Will the string be empty after processing?

Constraints

* 1 ≤ |s| ≤ 5 × 10^5
* s consists of lowercase English letters.
* 1 ≤ Q ≤ 10^5
* 1 ≤ l_i ≤ r_i ≤ |s|

Input

The input is given from Standard Input in the following format:


s
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q


Output

Print Q lines. The i-th line should contain the answer to the i-th query: `Yes` or `No`.

Examples

Input

axxxxza
2
1 7
2 6


Output

No
Yes


Input

aabcdefghijklmnopqrstuvwxyz
1
1 27


Output

Yes


Input

yzyyyzyzyyyz
8
1 6
7 12
1 12
6 11
1 1
1 3
4 9
3 8


Output

Yes
Yes
Yes
Yes
No
No
No
No

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

#define FOR(i,n)    for(lli i=0;i<(lli)(n);++i)
#define FORU(i,j,k) for(lli i=(j);i<=(lli)(k);++i)
#define FORD(i,j,k) for(lli i=(j);i>=(lli)(k);--i)

#define pb push_back
#define mt make_tuple

using namespace std;

using lli = long long int;
using pll = pair<lli, lli>;

using vi = vector<lli>;
using vvi = vector<vi>;
using pii = tuple<lli, lli>;
using vii = vector<pii>;
using vvii = vector<vii>;

#define X(a) get<0>(a)
#define Y(a) get<1>(a)
#define Z(a) get<2>(a)

string TYPE(const int*)          { return "%d";   }
string TYPE(const lli*)          { return "%lld"; }
string TYPE(const char*)         { return "%c";   }
string TYPE(const char**)        { return "%s";   }
string TYPE(const unsigned int*) { return "%u";   }

const int MAX_BUF = 5*100*1000+42;
char buf[MAX_BUF];

void RD() {}
template<typename T, typename... Args> 
void RD(T* v, Args... args)
{
    scanf((" " + TYPE(v)).c_str(), v);
    RD(args...);
}
template<typename... Args> 
void RD(string* v, Args... args)
{
    scanf(" %s", buf);
    (*v) = buf;
    RD(args...);
}

void PR(bool nl = true)
{ if(nl) printf("\n"); }
template<typename T, typename... Args> 
void PR(bool nl, T v, Args... args)
{
    printf((TYPE(&v) + " ").c_str(), v);
    PR(nl, args...);
}
template<typename... Args> 
void PR(bool nl, string& v, Args... args)
{
    printf("%s", v.c_str());
    PR(nl, args...);
}
template<typename... Args> 
void PR(Args... args)
{ PR(true, args...); }

const long long int oo = 1000*1000*1000;

struct Coord {
    int x, y;
    Coord(int x = 0, int y = 0) : x(x), y(y) {}
    Coord operator + (const Coord& droite) const
    { return Coord(x + droite.x, y + droite.y); }
};

struct AB {
    int k; vector<lli> arbre;
    AB(int _k = 20, lli def = 0) { k = _k;
        FOR(i, 1 << k)
            arbre.push_back(i < (1 << (k-1)) ? 0LL : def);
        FORD(i, ((1 << (k-1)) - 1), 1)
            arbre[i] = arbre[i << 1] + arbre[(i << 1) ^ 1];
    }
    void set(int i, lli x) { int feuille = i + (1 << (k-1));
        arbre[feuille] = x;
        iset(feuille >> 1);
    }
    void iset(int noeud) {
        if(noeud) {
            arbre[noeud] = arbre[noeud << 1] + arbre[(noeud << 1)  ^ 1];
            iset(noeud >> 1);
    }   }
    lli sum(int deb, int fin, int noeud = 1, int p = 0, int q = -1) {
        if(q < p) q = 1 << (k-1);
        if(deb <= p && q <= fin) return arbre[noeud];
        if(deb >= q || fin <= p) return 0LL;
        int mil = (p + q) / 2;
        return sum(deb, fin, noeud << 1, p, mil) + sum(deb, fin, (noeud << 1) ^ 1, mil, q);
    }
};

string s;
int dyn[27][5*100*1000+42];
int suiv[5*100*1000+42];
vector<int> prec[5*100*1000+42];
int vin[5*100*1000+42], vout[5*100*1000+42];
bool dejaVu[5*100*1000+42];
int cur;

void dfs(int n)
{
    assert(!dejaVu[n]);
    dejaVu[n] = true;
    vin[n] = cur++;
    for(auto v : prec[n])
        dfs(v);
    vout[n] = cur++;
}

int main()
{
    RD(&s);
    int n = s.length();
    FOR(i, 26)
        dyn[i][n] = -1;
    dyn[26][n] = n;
    FOR(i, n)
        suiv[i] = -1;
    FORD(i, n-1, 0)
    {
        FOR(j, 27)
        {
            dyn[j][i] = -1;
            if(s[i]-'a' == j)
                dyn[j][i] = i;
            else if(s[i]-'a' < j)
            {
                int rjm = dyn[j-1][i];
                if(rjm != -1)
                {
                    int rjm2 = dyn[j-1][rjm+1];
                    if(rjm2 != -1)
                        dyn[j][i] = rjm2;
                }
            }
            //printf("%2d%c", dyn[j][i], " \n"[j==26]);
        }
        FOR(j, 26)
        {
            if(dyn[26][i] != -1 && dyn[j][i] == -1)
                dyn[j][i] = dyn[j][dyn[26][i]+1];
        }
        suiv[i] = dyn[26][i] == -1 ? -1 : dyn[26][i]+1;
        if(suiv[i] != -1)
            prec[suiv[i]].push_back(i);
    }
    FORD(i, n, 0)
        if(!dejaVu[i])
            dfs(i);
    //FOR(i, n)
    //    PR(vin[i], vout[i]);
    int q;
    RD(&q);
    FOR(iq, q)
    {
        int a, b;
        RD(&a, &b);
        --a;
        PR(vin[b] <= vin[a] && vout[a] <= vout[b] ? "Yes" : "No");
    }
    return 0;
}