#include<bits/stdc++.h>
using namespace std;
class SuffixArray{
    void CreateBeginBucket(vector<int>&v,vector<int>&bucket){
        fill(bucket.begin(),bucket.end(),0);
        for(int i=0;i<v.size();i++)bucket[v[i]]++;
        int sum=0;
        for(int i=0;i<bucket.size();i++){bucket[i]+=sum;swap(sum,bucket[i]);}
    }

    void CreateEndBucket(vector<int>&v,vector<int>&bucket){
        fill(bucket.begin(),bucket.end(),0);
        for(int i=0;i<v.size();i++)bucket[v[i]]++;
        for(int i=1;i<bucket.size();i++)bucket[i]+=bucket[i-1];
    }

    void InducedSort(vector<int>&v,vector<int>&SA,int mv,vector<int>&bucket,vector<int>&isL){
        CreateBeginBucket(v,bucket);
        for(int i=0;i<v.size();i++)if(SA[i]>0&&isL[SA[i]-1])SA[bucket[v[SA[i]-1]]++]=SA[i]-1;
    }

    void InvertInducedSort(vector<int>&v,vector<int>&SA,int mv,vector<int>&bucket,vector<int>&isL){
        CreateEndBucket(v,bucket);
        for(int i=v.size()-1;i>=0;i--)if(SA[i]>0&&!isL[SA[i]-1])SA[--bucket[v[SA[i]-1]]]=SA[i]-1;
    }

    vector<int>SA_IS(vector<int>v,int mv){
        if(v.size()==1)return vector<int>(1,0);

        vector<int>isL(v.size());
        vector<int>bucket(mv+1);
        vector<int>SA(v.size(),-1);
        auto isLMS=[&](int x)->bool{return x>0&&isL[x-1]&&!isL[x];};

        isL[v.size()-1]=0;
        for(int i=v.size()-2;i>=0;i--)isL[i]=v[i]>v[i+1]||(v[i]==v[i+1]&&isL[i+1]);
        CreateEndBucket(v,bucket);
        for(int i=0;i<v.size();i++)if(isLMS(i))SA[--bucket[v[i]]]=i;
        InducedSort(v,SA,mv,bucket,isL);
        InvertInducedSort(v,SA,mv,bucket,isL);

        int cur=0;
        vector<int>ord(v.size());
        for(int i=0;i<v.size();i++)if(isLMS(i))ord[i]=cur++;

        vector<int>nxv(cur);
        cur=-1;
        int prev=-1;
        for(int i=0;i<v.size();i++){
            if(!isLMS(SA[i]))continue;
            bool diff=false;
            for(int d=0;d<v.size();d++){
                if(prev==-1||v[SA[i]+d]!=v[prev+d]||isL[SA[i]+d]!=isL[prev+d]){
                    diff=true;
                    break;
                }
                else if(d>0&&isLMS(SA[i]+d))break;
            }
            if(diff){cur++;prev=SA[i];}
            nxv[ord[SA[i]]]=cur;
        }

        vector<int>reord(nxv.size());
        for(int i=0;i<v.size();i++)if(isLMS(i))reord[ord[i]]=i;
        vector<int>nxSA=SA_IS(nxv,cur);
        CreateEndBucket(v,bucket);
        for(int i=0;i<SA.size();i++)SA[i]=-1;
        for(int i=nxSA.size()-1;i>=0;i--)SA[--bucket[v[reord[nxSA[i]]]]]=reord[nxSA[i]];
        InducedSort(v,SA,mv,bucket,isL);
        InvertInducedSort(v,SA,mv,bucket,isL);
        return SA;
    }

    vector<int>SA_IS(string s){
        vector<int>v(s.size()+1);
        for(int i=0;i<s.size();i++)v[i]=s[i]+1;
        return SA_IS(v,*max_element(v.begin(),v.end()));
    }

    vector<int>construct_lcp(string &s,vector<int>&sa){
        vector<int>lcp,rank(s.size()+1);
        int n=s.size();
        for(int i=0;i<=n;i++)rank[sa[i]]=i;

        int h=0;
        lcp[0]=0;
        for(int i=0;i<n;i++){
            int j=sa[rank[i]-1];

            if(h>0)h--;
            for(;j+h<n&&i+h<n;h++){
                if(s[j+h]!=s[i+h])break;
            }
            lcp[rank[i]-1]=h;
        }
        return lcp;
    }

    class SparseTable{
        vector<vector<int> >st;
    public:
        void init(vector<int>vec){
            int b;
            for(b=0;(1<<b)<vec.size();b++);
            st.assign(b,vector<int>(1<<b));
            for(int i=0;i<vec.size();i++)st[0][i]=vec[i];

            for(int i=1;i<b;i++){
                for(int j=0;j+(1<<i)<=(1<<b);j++){
                    st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
                }
            }
        }
        int GetMin(int l,int r){
            assert(l<r);
            int b=32-__builtin_clz(r-l)-1;
            return min(st[b][l],st[b][r-(1<<b)]);
        }
        SparseTable(){}
        SparseTable(vector<int>vec){init(vec);}
    };
    SparseTable st;
public:
    string s;
    vector<int>sa,lcp;
    void init(string &T){
        s=T;
        sa=SA_IS(s);
        //lcp=construct_lcp(s,sa);cout<<"malta"<<endl;
        //st.init(lcp);cout<<"ok"<<endl;
    }
    SuffixArray(string &t){init(t);}
    SuffixArray(){}

    bool contain(string &t){
        int a=0,b=s.size();
        while(b-a>1){
            int c=(a+b)/2;
            if(s.compare(sa[c],t.size(),t)<0)a=c;
            else b=c;
        }
        return s.compare(sa[b],t.size(),t)==0;
    }
};

signed main(){
    string S,T;
    int Q;
    cin>>S>>Q;
    SuffixArray SA(S);

    while(Q--){
        cin>>T;
        cout<<SA.contain(T)<<endl;
    }
    return 0;
}
### Prompt

Develop a solution in CPP to the problem described below:

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;
class SuffixArray{
    void CreateBeginBucket(vector<int>&v,vector<int>&bucket){
        fill(bucket.begin(),bucket.end(),0);
        for(int i=0;i<v.size();i++)bucket[v[i]]++;
        int sum=0;
        for(int i=0;i<bucket.size();i++){bucket[i]+=sum;swap(sum,bucket[i]);}
    }

    void CreateEndBucket(vector<int>&v,vector<int>&bucket){
        fill(bucket.begin(),bucket.end(),0);
        for(int i=0;i<v.size();i++)bucket[v[i]]++;
        for(int i=1;i<bucket.size();i++)bucket[i]+=bucket[i-1];
    }

    void InducedSort(vector<int>&v,vector<int>&SA,int mv,vector<int>&bucket,vector<int>&isL){
        CreateBeginBucket(v,bucket);
        for(int i=0;i<v.size();i++)if(SA[i]>0&&isL[SA[i]-1])SA[bucket[v[SA[i]-1]]++]=SA[i]-1;
    }

    void InvertInducedSort(vector<int>&v,vector<int>&SA,int mv,vector<int>&bucket,vector<int>&isL){
        CreateEndBucket(v,bucket);
        for(int i=v.size()-1;i>=0;i--)if(SA[i]>0&&!isL[SA[i]-1])SA[--bucket[v[SA[i]-1]]]=SA[i]-1;
    }

    vector<int>SA_IS(vector<int>v,int mv){
        if(v.size()==1)return vector<int>(1,0);

        vector<int>isL(v.size());
        vector<int>bucket(mv+1);
        vector<int>SA(v.size(),-1);
        auto isLMS=[&](int x)->bool{return x>0&&isL[x-1]&&!isL[x];};

        isL[v.size()-1]=0;
        for(int i=v.size()-2;i>=0;i--)isL[i]=v[i]>v[i+1]||(v[i]==v[i+1]&&isL[i+1]);
        CreateEndBucket(v,bucket);
        for(int i=0;i<v.size();i++)if(isLMS(i))SA[--bucket[v[i]]]=i;
        InducedSort(v,SA,mv,bucket,isL);
        InvertInducedSort(v,SA,mv,bucket,isL);

        int cur=0;
        vector<int>ord(v.size());
        for(int i=0;i<v.size();i++)if(isLMS(i))ord[i]=cur++;

        vector<int>nxv(cur);
        cur=-1;
        int prev=-1;
        for(int i=0;i<v.size();i++){
            if(!isLMS(SA[i]))continue;
            bool diff=false;
            for(int d=0;d<v.size();d++){
                if(prev==-1||v[SA[i]+d]!=v[prev+d]||isL[SA[i]+d]!=isL[prev+d]){
                    diff=true;
                    break;
                }
                else if(d>0&&isLMS(SA[i]+d))break;
            }
            if(diff){cur++;prev=SA[i];}
            nxv[ord[SA[i]]]=cur;
        }

        vector<int>reord(nxv.size());
        for(int i=0;i<v.size();i++)if(isLMS(i))reord[ord[i]]=i;
        vector<int>nxSA=SA_IS(nxv,cur);
        CreateEndBucket(v,bucket);
        for(int i=0;i<SA.size();i++)SA[i]=-1;
        for(int i=nxSA.size()-1;i>=0;i--)SA[--bucket[v[reord[nxSA[i]]]]]=reord[nxSA[i]];
        InducedSort(v,SA,mv,bucket,isL);
        InvertInducedSort(v,SA,mv,bucket,isL);
        return SA;
    }

    vector<int>SA_IS(string s){
        vector<int>v(s.size()+1);
        for(int i=0;i<s.size();i++)v[i]=s[i]+1;
        return SA_IS(v,*max_element(v.begin(),v.end()));
    }

    vector<int>construct_lcp(string &s,vector<int>&sa){
        vector<int>lcp,rank(s.size()+1);
        int n=s.size();
        for(int i=0;i<=n;i++)rank[sa[i]]=i;

        int h=0;
        lcp[0]=0;
        for(int i=0;i<n;i++){
            int j=sa[rank[i]-1];

            if(h>0)h--;
            for(;j+h<n&&i+h<n;h++){
                if(s[j+h]!=s[i+h])break;
            }
            lcp[rank[i]-1]=h;
        }
        return lcp;
    }

    class SparseTable{
        vector<vector<int> >st;
    public:
        void init(vector<int>vec){
            int b;
            for(b=0;(1<<b)<vec.size();b++);
            st.assign(b,vector<int>(1<<b));
            for(int i=0;i<vec.size();i++)st[0][i]=vec[i];

            for(int i=1;i<b;i++){
                for(int j=0;j+(1<<i)<=(1<<b);j++){
                    st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
                }
            }
        }
        int GetMin(int l,int r){
            assert(l<r);
            int b=32-__builtin_clz(r-l)-1;
            return min(st[b][l],st[b][r-(1<<b)]);
        }
        SparseTable(){}
        SparseTable(vector<int>vec){init(vec);}
    };
    SparseTable st;
public:
    string s;
    vector<int>sa,lcp;
    void init(string &T){
        s=T;
        sa=SA_IS(s);
        //lcp=construct_lcp(s,sa);cout<<"malta"<<endl;
        //st.init(lcp);cout<<"ok"<<endl;
    }
    SuffixArray(string &t){init(t);}
    SuffixArray(){}

    bool contain(string &t){
        int a=0,b=s.size();
        while(b-a>1){
            int c=(a+b)/2;
            if(s.compare(sa[c],t.size(),t)<0)a=c;
            else b=c;
        }
        return s.compare(sa[b],t.size(),t)==0;
    }
};

signed main(){
    string S,T;
    int Q;
    cin>>S>>Q;
    SuffixArray SA(S);

    while(Q--){
        cin>>T;
        cout<<SA.contain(T)<<endl;
    }
    return 0;
}
```