#include <bits/stdc++.h>
#define ll long long
#define V vector<long long>
#define VV vector<vector<long long>>
#define rep(i,n) for(ll (i)=0;(i)<(n);++(i))
using namespace std;

struct suffix_array{

    int n,logn;
    string s;
    vector<int> rank,sa,lcp;

    suffix_array(string &str):s(str){
        build_suffix_array();
        build_lcp();
    }

    void build_suffix_array(){
        n=s.size();
        logn=floor(log2(n));
        rank.resize(n);
        sa.resize(n);
        for(int i=0;i<n;++i){
            rank[i]=s[i];
            sa[i]=i;
        }
        for(int k=0;k<=logn;++k){
            auto comp=[&](int a,int b){
                if(rank[a]!=rank[b])return rank[a]<rank[b];
                a=(a+(1<<k)<n)?rank[a+(1<<k)]:-1;
                b=(b+(1<<k)<n)?rank[b+(1<<k)]:-1;
                return a<b;
            };
            sort(sa.begin(),sa.end(),comp);
            vector<int> tmp=rank;
            tmp[sa[0]]=0;
            for(int i=1;i<n;++i)tmp[sa[i]]=tmp[sa[i-1]]+comp(sa[i-1],sa[i]);
            rank=tmp;
        }
    }

    void build_lcp(){
        vector<int> tmp(n);
        for(int i=0;i<n;++i){
            tmp[sa[i]]=i;
        }
        int h=0;
        lcp.resize(n);
        for(int i=0;i<n;++i){
            if(tmp[i]==0){
                lcp[0]=0;
                if(h>0)h--;
                continue;
            }
            int j=sa[tmp[i]-1];
            if(h>0)h--;
            for(;i+h<n&&j+h<n;++h){
                if(s[i+h]!=s[j+h])break;
            }
            lcp[tmp[i]]=h;
        }
    }

    int compare(string t,int s_idx=0,int t_idx=0){
        while(s_idx<s.size()&&t_idx<t.size()){
            if(s[s_idx]<t[t_idx]){
                return 1;
            }else if(s[s_idx]>t[t_idx]){
                return -1;
            }
            s_idx++;
            t_idx++;
        }
        if(t_idx>=t.size()){
            return 0;
        }else{
            if(s_idx>=s.size()){
                return 1;
            }else{
                return -1;
            }
        }
    }

    int lower_bound(string t){
        int l=0;
        int r=n-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(compare(t,sa[mid])>0){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return l;
    }

    int upper_bound(string t){
        int l=0;
        int r=n-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(compare(t,sa[mid])>=0){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return l;
    }

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

    int size()const{
        return n;
    }

};

ll num(ll a){
    return a*(a+1)/2;
}

int main(){
    string s;
    cin>>s;
    suffix_array sa(s);
    ll n;
    cin>>n;
    rep(i,n){
        string t;
        cin>>t;
        cout<<(sa.upper_bound(t)!=sa.lower_bound(t))<<endl;
    }
}


### Prompt

Please create a solution in CPP 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>
#define ll long long
#define V vector<long long>
#define VV vector<vector<long long>>
#define rep(i,n) for(ll (i)=0;(i)<(n);++(i))
using namespace std;

struct suffix_array{

    int n,logn;
    string s;
    vector<int> rank,sa,lcp;

    suffix_array(string &str):s(str){
        build_suffix_array();
        build_lcp();
    }

    void build_suffix_array(){
        n=s.size();
        logn=floor(log2(n));
        rank.resize(n);
        sa.resize(n);
        for(int i=0;i<n;++i){
            rank[i]=s[i];
            sa[i]=i;
        }
        for(int k=0;k<=logn;++k){
            auto comp=[&](int a,int b){
                if(rank[a]!=rank[b])return rank[a]<rank[b];
                a=(a+(1<<k)<n)?rank[a+(1<<k)]:-1;
                b=(b+(1<<k)<n)?rank[b+(1<<k)]:-1;
                return a<b;
            };
            sort(sa.begin(),sa.end(),comp);
            vector<int> tmp=rank;
            tmp[sa[0]]=0;
            for(int i=1;i<n;++i)tmp[sa[i]]=tmp[sa[i-1]]+comp(sa[i-1],sa[i]);
            rank=tmp;
        }
    }

    void build_lcp(){
        vector<int> tmp(n);
        for(int i=0;i<n;++i){
            tmp[sa[i]]=i;
        }
        int h=0;
        lcp.resize(n);
        for(int i=0;i<n;++i){
            if(tmp[i]==0){
                lcp[0]=0;
                if(h>0)h--;
                continue;
            }
            int j=sa[tmp[i]-1];
            if(h>0)h--;
            for(;i+h<n&&j+h<n;++h){
                if(s[i+h]!=s[j+h])break;
            }
            lcp[tmp[i]]=h;
        }
    }

    int compare(string t,int s_idx=0,int t_idx=0){
        while(s_idx<s.size()&&t_idx<t.size()){
            if(s[s_idx]<t[t_idx]){
                return 1;
            }else if(s[s_idx]>t[t_idx]){
                return -1;
            }
            s_idx++;
            t_idx++;
        }
        if(t_idx>=t.size()){
            return 0;
        }else{
            if(s_idx>=s.size()){
                return 1;
            }else{
                return -1;
            }
        }
    }

    int lower_bound(string t){
        int l=0;
        int r=n-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(compare(t,sa[mid])>0){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return l;
    }

    int upper_bound(string t){
        int l=0;
        int r=n-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(compare(t,sa[mid])>=0){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return l;
    }

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

    int size()const{
        return n;
    }

};

ll num(ll a){
    return a*(a+1)/2;
}

int main(){
    string s;
    cin>>s;
    suffix_array sa(s);
    ll n;
    cin>>n;
    rep(i,n){
        string t;
        cin>>t;
        cout<<(sa.upper_bound(t)!=sa.lower_bound(t))<<endl;
    }
}


```