#include "bits/stdc++.h"

using namespace std;

struct SuffixArray
{
    int sz;
    string s;
    vector<int> rank,sa;
    // vector<int> lcp,lcp_rank;

    SuffixArray(string str){
        s=str;
        sz=str.length();
        rank.resize(sz+1);
        sa.resize(sz+1);
        // lcp.resize(sz+1);
        // lcp_rank.resize(sz+1);
        build();
        // build_lcp();
    }

    void build(){
        for(int i=0;i<=sz;i++){
            sa[i] = i;
            rank[i] = i < sz ? s[i] : -1;
        }

        int k;
        auto compare = [&](int i, int j) {
            if (rank[i] != rank[j]) return rank[i] < rank[j];
            else {
                int ri = i + k <= sz ? rank[i + k] : -1;
                int rj = j + k <= sz ? rank[j + k] : -1;
                return ri < rj;
            }
        };

        vector<int> tmp(sz+1);
        for(k=1;k<=sz;k*=2){
            sort(sa.begin(),sa.end(),compare);
            tmp[sa[0]] = 0;
            for(int i=1;i<=sz;i++){
                tmp[sa[i]] = tmp[sa[i-1]] + (compare(sa[i-1],sa[i]) ? 1 : 0);
            }
            for(int i=0;i<=sz;i++){
                rank[i] = tmp[i];
            }
        }
    }
    // s縺荊繧貞性繧?縺?
    bool contains(string t){
        int l=0,r=sz;
        while(r-l>1){
            int mid=(l+r)/2;
            if(s.substr(sa[mid],t.length())<t) l=mid;
            else r=mid;
        }
        return s.substr(sa[r],t.size()) ==t;
    }
    /*
    void build_lcp(){
        for(int i=0;i<=sz;i++) lcp_rank[sa[i]]=i;
        int h=0;
        lcp[0]=0;
        for(int i=0;i<sz;i++){
            int j=sa[rank[i]-1];

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

int main(){
    string s;
    cin>>s;
    int n;
    cin>>n;
    SuffixArray sa(s);
    for(int i=0;i<n;++i){
        string sc;
        cin>>sc;
        if(sa.contains(sc))cout<<"1"<<endl;
        else cout<<"0"<<endl;
    }
}
### 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;

struct SuffixArray
{
    int sz;
    string s;
    vector<int> rank,sa;
    // vector<int> lcp,lcp_rank;

    SuffixArray(string str){
        s=str;
        sz=str.length();
        rank.resize(sz+1);
        sa.resize(sz+1);
        // lcp.resize(sz+1);
        // lcp_rank.resize(sz+1);
        build();
        // build_lcp();
    }

    void build(){
        for(int i=0;i<=sz;i++){
            sa[i] = i;
            rank[i] = i < sz ? s[i] : -1;
        }

        int k;
        auto compare = [&](int i, int j) {
            if (rank[i] != rank[j]) return rank[i] < rank[j];
            else {
                int ri = i + k <= sz ? rank[i + k] : -1;
                int rj = j + k <= sz ? rank[j + k] : -1;
                return ri < rj;
            }
        };

        vector<int> tmp(sz+1);
        for(k=1;k<=sz;k*=2){
            sort(sa.begin(),sa.end(),compare);
            tmp[sa[0]] = 0;
            for(int i=1;i<=sz;i++){
                tmp[sa[i]] = tmp[sa[i-1]] + (compare(sa[i-1],sa[i]) ? 1 : 0);
            }
            for(int i=0;i<=sz;i++){
                rank[i] = tmp[i];
            }
        }
    }
    // s縺荊繧貞性繧?縺?
    bool contains(string t){
        int l=0,r=sz;
        while(r-l>1){
            int mid=(l+r)/2;
            if(s.substr(sa[mid],t.length())<t) l=mid;
            else r=mid;
        }
        return s.substr(sa[r],t.size()) ==t;
    }
    /*
    void build_lcp(){
        for(int i=0;i<=sz;i++) lcp_rank[sa[i]]=i;
        int h=0;
        lcp[0]=0;
        for(int i=0;i<sz;i++){
            int j=sa[rank[i]-1];

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

int main(){
    string s;
    cin>>s;
    int n;
    cin>>n;
    SuffixArray sa(s);
    for(int i=0;i<n;++i){
        string sc;
        cin>>sc;
        if(sa.contains(sc))cout<<"1"<<endl;
        else cout<<"0"<<endl;
    }
}
```