#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}


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;
}

template<class T>
vector<int>SA_IS(T s){
    vector<int>ss(s.size()+1);
    for(int i=0;i<s.size();i++)ss[i]=s[i]+1;
    int mv=*max_element(ss.begin(),ss.end());
    return SA_IS(ss,mv);
}

bool contain(string &S,vector<int>&sa,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;cin>>s;
    vector<int>sa=SA_IS(s);
    int Q;cin>>Q;
    while(Q--){
        string t;cin>>t;
        cout<<contain(s,sa,t)<<endl;
    }
    return 0;
}
### Prompt

Please formulate a CPP solution to the following problem:

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;

#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}


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;
}

template<class T>
vector<int>SA_IS(T s){
    vector<int>ss(s.size()+1);
    for(int i=0;i<s.size();i++)ss[i]=s[i]+1;
    int mv=*max_element(ss.begin(),ss.end());
    return SA_IS(ss,mv);
}

bool contain(string &S,vector<int>&sa,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;cin>>s;
    vector<int>sa=SA_IS(s);
    int Q;cin>>Q;
    while(Q--){
        string t;cin>>t;
        cout<<contain(s,sa,t)<<endl;
    }
    return 0;
}
```