#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

//空文字列はなし！
//forever ei1333
class SuffixArray{
    vec<int> SA;
    const string S;
    int N;
public:
    SuffixArray(const string& S):S(S){
        N = S.size();
        SA.resize(N);
        iota(SA.begin(),SA.end(),0);
        sort(SA.begin(),SA.end(),[&](int i,int j){
            return S[i]==S[j]? i>j:S[i]<S[j];
        });
        vec<int> classes(N),C(S.begin(),S.end()),cnt(S.size());
        for(int len=1;len<N;len<<=1){
            for(int i=0;i<N;i++){
                if(i>0 && C[SA[i-1]]==C[SA[i]] && 
                SA[i-1]+len<N && C[SA[i-1]+len/2]==C[SA[i]+len/2]){
                    classes[SA[i]] = classes[SA[i-1]];
                }else{
                    classes[SA[i]] = i;
                }
            }
            iota(cnt.begin(),cnt.end(),0);
            copy(SA.begin(),SA.end(),C.begin());
            for(int i=0;i<N;i++){
                int sl = C[i]-len;
                if(sl>=0) SA[cnt[classes[sl]]++] = sl;
            }
            classes.swap(C);
        }
    }

    int operator[](int k)const{
        return SA[k];
    }

    int size()const{
        return N;
    }

    bool lt_substr(const string& T,int si=0,int ti=0){
        int sn = N,tn = T.size();
        while(si<sn && ti<tn){
            if(S[si]<T[ti]) return true;
            if(S[si]>T[ti]) return false;
            si++; ti++;
        }
        return si>=sn && ti<tn;
    }

    int lower_bound(const string& T,int si=0,int ti=0){
        int l = -1,r = N;
        while(l+1<r){
            int m = (l+r)>>1;
            (lt_substr(T,SA[m])? l:r) = m;
        }
        return r;
    }

    P<int,int> lower_upper_bound(string& T){
        int id = lower_bound(T);
        int l = id-1,r = N;
        T.back()++;
        while(l+1<r){
            int m = (l+r)>>1;
            (lt_substr(T,SA[m])? l:r) = m;
        }
        T.back()--;
        return {id,r};
    }

};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    SuffixArray SA(S);
    int Q;
    cin >> Q;
    for(int i=0;i<Q;i++){
        string T;
        cin >> T;
        auto r = (SA.lower_upper_bound(T));
        cout << (r.first!=r.second) << endl;
    }
}

### Prompt

Construct a CPP code solution to the problem outlined:

Determine whether a text T includes a pattern P. Your program should answer for given queries consisting of P_i.

Constraints

* 1 ≤ length of T ≤ 1000000
* 1 ≤ length of P_i ≤ 1000
* 1 ≤ Q ≤ 10000
* The input consists of alphabetical characters and digits

Input

In the first line, a text T is given. In the second line, an integer Q denoting the number of queries is given. In the following Q lines, the patterns P_i are given respectively.

Output

For each question, print 1 if the text includes P_i, or print 0 otherwise.

Example

Input

aabaaa
4
aa
ba
bb
xyz


Output

1
1
0
0

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

//空文字列はなし！
//forever ei1333
class SuffixArray{
    vec<int> SA;
    const string S;
    int N;
public:
    SuffixArray(const string& S):S(S){
        N = S.size();
        SA.resize(N);
        iota(SA.begin(),SA.end(),0);
        sort(SA.begin(),SA.end(),[&](int i,int j){
            return S[i]==S[j]? i>j:S[i]<S[j];
        });
        vec<int> classes(N),C(S.begin(),S.end()),cnt(S.size());
        for(int len=1;len<N;len<<=1){
            for(int i=0;i<N;i++){
                if(i>0 && C[SA[i-1]]==C[SA[i]] && 
                SA[i-1]+len<N && C[SA[i-1]+len/2]==C[SA[i]+len/2]){
                    classes[SA[i]] = classes[SA[i-1]];
                }else{
                    classes[SA[i]] = i;
                }
            }
            iota(cnt.begin(),cnt.end(),0);
            copy(SA.begin(),SA.end(),C.begin());
            for(int i=0;i<N;i++){
                int sl = C[i]-len;
                if(sl>=0) SA[cnt[classes[sl]]++] = sl;
            }
            classes.swap(C);
        }
    }

    int operator[](int k)const{
        return SA[k];
    }

    int size()const{
        return N;
    }

    bool lt_substr(const string& T,int si=0,int ti=0){
        int sn = N,tn = T.size();
        while(si<sn && ti<tn){
            if(S[si]<T[ti]) return true;
            if(S[si]>T[ti]) return false;
            si++; ti++;
        }
        return si>=sn && ti<tn;
    }

    int lower_bound(const string& T,int si=0,int ti=0){
        int l = -1,r = N;
        while(l+1<r){
            int m = (l+r)>>1;
            (lt_substr(T,SA[m])? l:r) = m;
        }
        return r;
    }

    P<int,int> lower_upper_bound(string& T){
        int id = lower_bound(T);
        int l = id-1,r = N;
        T.back()++;
        while(l+1<r){
            int m = (l+r)>>1;
            (lt_substr(T,SA[m])? l:r) = m;
        }
        T.back()--;
        return {id,r};
    }

};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    SuffixArray SA(S);
    int Q;
    cin >> Q;
    for(int i=0;i<Q;i++){
        string T;
        cin >> T;
        auto r = (SA.lower_upper_bound(T));
        cout << (r.first!=r.second) << endl;
    }
}

```