#include "bits/stdc++.h"

using namespace std;

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

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

    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];
            }
        }
    }
    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 print(){
        for(int i=0;i<sz;i++){
            cout<<s.substr(sa[i])<<endl;
        }
    }
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

    string t;cin>>t;
    int q;cin>>q;
    SuffixArray sf(t);
    //sf.print();
    for(int i=0;i<q;i++){
        string p;cin>>p;
        cout<<sf.contains(p)<<endl;
    }
}
### Prompt

In cpp, your task is to solve 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;

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

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

    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];
            }
        }
    }
    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 print(){
        for(int i=0;i<sz;i++){
            cout<<s.substr(sa[i])<<endl;
        }
    }
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

    string t;cin>>t;
    int q;cin>>q;
    SuffixArray sf(t);
    //sf.print();
    for(int i=0;i<q;i++){
        string p;cin>>p;
        cout<<sf.contains(p)<<endl;
    }
}
```