#include <cstdlib>
#include <string>
#include <iostream>
#include <vector>
using namespace std;

unsigned char mask[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
#define tget(i) ( (t[(i)/8]&mask[(i)%8]) ? 1 : 0 )
#define tset(i, b) t[(i)/8]=(b) ? (mask[(i)%8]|t[(i)/8]) : ((~mask[(i)%8])&t[(i)/8])
#define chr(i) (cs==sizeof(int)?((int*)s)[i]:((unsigned char *)s)[i])
#define isLMS(i) (i>0 && tget(i) && !tget(i-1))

// find the start or end of each bucket
void getBuckets(unsigned char *s, int *bkt, int n, int K, int cs, bool end) {
    int i, sum = 0;
    for (i = 0; i <= K; i++)
        bkt[i] = 0; // clear all buckets
    for (i = 0; i < n; i++)
        bkt[chr(i)]++; // compute the size of each bucket
    for (i = 0; i <= K; i++) {
        sum += bkt[i];
        bkt[i] = end ? sum : sum - bkt[i];
    }
}
// compute SAl
void induceSAl(unsigned char *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) {
    int i, j;
    getBuckets(s, bkt, n, K, cs, end); // find starts of buckets
    for (i = 0; i < n; i++) {
        j = SA[i] - 1;
        if (j >= 0 && !tget(j))
            SA[bkt[chr(j)]++] = j;
    }
}
// compute SAs
void induceSAs(unsigned char *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) {
    int i, j;
    getBuckets(s, bkt, n, K, cs, end); // find ends of buckets
    for (i = n - 1; i >= 0; i--) {
        j = SA[i] - 1;
        if (j >= 0 && tget(j))
            SA[--bkt[chr(j)]] = j;
    }
}

// find the suffix array SA of s[0..n-1] in {1..K}^n
// require s[n-1]=0 (the sentinel!), n>=2
// use a working space (excluding s and SA) of at most 2.25n+O(1) for a constant alphabet
void SA_IS(unsigned char *s, int *SA, int n, int K, int cs) {
    int i, j;
    unsigned char *t = (unsigned char *) malloc(n / 8 + 1); // LS-type array in bits
    // Classify the type of each character
    tset(n-2, 0);
    tset(n-1, 1); // the sentinel must be in s1, important!!!
    for (i = n - 3; i >= 0; i--)
        tset(i, (chr(i)<chr(i+1) || (chr(i)==chr(i+1) && tget(i+1)==1))?1:0);
    // stage 1: reduce the problem by at least 1/2
    // sort all the S-substrings
    int *bkt = (int *) malloc(sizeof(int) * (K + 1)); // bucket array
    getBuckets(s, bkt, n, K, cs, true); // find ends of buckets
    for (i = 0; i < n; i++)
        SA[i] = -1;
    for (i = 1; i < n; i++)
        if (isLMS(i))
            SA[--bkt[chr(i)]] = i;
    induceSAl(t, SA, s, bkt, n, K, cs, false);
    induceSAs(t, SA, s, bkt, n, K, cs, true);
    free(bkt);
    // compact all the sorted substrings into the first n1 items of SA
    // 2*n1 must be not larger than n (proveable)
    int n1 = 0;
    for (i = 0; i < n; i++)
        if (isLMS(SA[i]))
            SA[n1++] = SA[i];
    // find the lexicographic names of all substrings
    for (i = n1; i < n; i++)
        SA[i] = -1; // init the name array buffer
    int name = 0, prev = -1;
    for (i = 0; i < n1; i++) {
        int pos = SA[i];
        bool diff = false;
        for (int d = 0; d < n; d++)
            if (prev == -1 || chr(pos+d) != chr(prev+d) || tget(pos+d) != tget(prev+d)) {
                diff = true;
                break;
            } else if (d > 0 && (isLMS(pos+d) || isLMS(prev+d)))
                break;
        if (diff) {
            name++;
            prev = pos;
        }
        pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
        SA[n1 + pos] = name - 1;
    }
    for (i = n - 1, j = n - 1; i >= n1; i--)
        if (SA[i] >= 0)
            SA[j--] = SA[i];
    // stage 2: solve the reduced problem
    // recurse if names are not yet unique
    int *SA1 = SA, *s1 = SA + n - n1;
    if (name < n1)
        SA_IS((unsigned char*) s1, SA1, n1, name - 1, sizeof(int));
    else
        // generate the suffix array of s1 directly
        for (i = 0; i < n1; i++)
            SA1[s1[i]] = i;
    // stage 3: induce the result for the original problem
    bkt = (int *) malloc(sizeof(int) * (K + 1)); // bucket array
    // put all left-most S characters into their buckets
    getBuckets(s, bkt, n, K, cs, true); // find ends of buckets
    for (i = 1, j = 0; i < n; i++)
        if (isLMS(i))
            s1[j++] = i; // get p1
    for (i = 0; i < n1; i++)
        SA1[i] = s1[SA1[i]]; // get index in s
    for (i = n1; i < n; i++)
        SA[i] = -1; // init SA[n1..n-1]
    for (i = n1 - 1; i >= 0; i--) {
        j = SA[i];
        SA[i] = -1;
        SA[--bkt[chr(j)]] = j;
    }
    induceSAl(t, SA, s, bkt, n, K, cs, false);
    induceSAs(t, SA, s, bkt, n, K, cs, true);
    free(bkt);
    free(t);
}

const int maxn = 1000100;
int sa[maxn];
int lcp[maxn];
int pos[maxn];
unsigned char *s;
int n;

void calc_lcp() {
    for (int i = 0; i < n+1; i++)
        pos[sa[i]] = i;
    for (int i = 0, h = 0; i < n+1; i++) {
        if (pos[i] < n ) {
            for (int j = sa[pos[i] + 1]; s[i + h] == s[j + h]; ++h)
                ;
            lcp[pos[i]] = h;
            if (h > 0)
                --h;
        }
    }
}
/*
 str="abcab" n=5
 SA_IS(str,sa,n+1,256,1)
 calc_lcp()
 sa={5,3,0,4,1,2}
 str.subtring(sa)={"","ab","abcab","b","bcab","cab"}
 lcp={0,2,0,1,0,0}
 pos={2,4,5,1,3,0}
*/

pair<int,int> longest_repeated_substring(int overlap){
    //overlap=1 non-overlapping , overlap=0 overlap allowed
    int maxl=0,maxidx=-1;
    for(int i=1;i<n+1;i++){
        if(lcp[i]>maxl) {
            if(overlap && abs(sa[i]-sa[i-1])<lcp[i]) continue;
            maxl=lcp[i];
            maxidx=sa[i];
        }
    }
    if(maxidx==-1) return make_pair(-1,-1);
    return make_pair(maxidx,maxl);
}
pair<pair<int,int>,int> longest_k_repeated_substring(string str,int k){
    k--;
    for (int i = 0; i < n+1; i++)
        pos[sa[i]] = i;
    int maxl=0,maxidx=-1,rightmostidx=0;
    for (int i = 0, h = 0; i < n+1; i++) {
        if (pos[i] < n +1-k) {
            for (int j = sa[pos[i] + k]; s[i + h] == s[j + h]; ++h)
                ;
            if(h>=maxl){
                if(h>maxl) rightmostidx=sa[pos[i] + k];
                maxl=h;
                maxidx=i;
                if(rightmostidx<sa[pos[i] + k]) rightmostidx=sa[pos[i] + k];
            }
            //cout<<i<<" "<<h<<" "<<str.substr(i,h)<<maxl<<" "<<str.substr(maxidx,maxl)<<" "<<rightmostidx<<endl;

            if (h > 0)
                --h;
        }
    }
    if(maxidx==-1) return make_pair(make_pair(-1,-1),-1);
    return make_pair(make_pair(rightmostidx,maxidx),maxl);
}
pair<pair<int,int>,pair<int,int> > longest_common_substring(string str1,string str2){
    string str=str1+" "+str2;
    s = (unsigned char*) str.c_str();
    n = (int)str.size();
    SA_IS(s, sa, n + 1, 256, 1);
    calc_lcp();
    pair<int,int> p=longest_repeated_substring(0);
    int indx2=sa[pos[p.first]+1];
    //cout<<str.substr(p.first,p.second)<<" "<<str.substr(indx2,p.second)<<endl;
    if((p.first<str1.length()&&indx2<str1.length())||(p.first>str1.length()&&indx2>str1.length()) || str.substr(p.first,p.second)!=str.substr(indx2,p.second)) {
                return make_pair(make_pair(0,0),p);
    }
    return make_pair(p,make_pair(indx2,p.second));
}

pair<int,int> smallest_lex_rotation(string str){
    
    str=str+str;
    s = (unsigned char*) str.c_str();
    
    n = (int)str.size();
    SA_IS(s, sa, n + 1, 256, 1);
    for(int i=1;i<n+1;i++){
        //cout<<str.substr(sa[i])<<" "<<sa[i]<<"\n";
    }
    
    int minval=maxn;
    for(int i=0;i<n+1;i++){
        if(sa[i]<=n/2){
            while(i<n && sa[i]<=n/2 && str.substr(sa[i],n/2)==str.substr(sa[i+1],n/2)){
                if(minval>sa[i]) minval=sa[i];
                //printf("i %d\n",i);
                i++;
            }
            return make_pair(sa[i],n/2);
        }
    }
    
    return make_pair(-1,n/2);
}

long count_distinct_substrings(string str){
    s = (unsigned char*) str.c_str();
    n = (int)str.size();
    SA_IS(s, sa, n + 1, 256, 1);
    calc_lcp();
    long count=0;
    for(int i=1;i<n+1;i++) count+=n-sa[i]-lcp[i];
    return count;
}

pair<int,int> longest_palindromic_substring(string str){
    string revstr=string(str.rbegin(),str.rend());
    return longest_common_substring(str, revstr).first;
}

bool contain(string str, int *sa, string T){
    int a = 0, b = str.length();
    while( b - a > 1 ){
        int c = (a + b ) / 2;
        if ( str.compare(sa[c], T.length(), T) < 0 ) a = c;
        else b = c;
    }
    return str.compare(sa[b], T.length(), T) == 0;
}


int main() {
    string str;
    cin>>str;
    s = (unsigned char*) str.c_str();
    n = (int)str.size();
    SA_IS(s, sa, n + 1, 256, 1);
    int t;
    cin>>t;
    while(t--){
    	string pat;
    	cin>>pat;
    	cout<<contain(str,sa,pat)<<"\n";
    }
}
### 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 <cstdlib>
#include <string>
#include <iostream>
#include <vector>
using namespace std;

unsigned char mask[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
#define tget(i) ( (t[(i)/8]&mask[(i)%8]) ? 1 : 0 )
#define tset(i, b) t[(i)/8]=(b) ? (mask[(i)%8]|t[(i)/8]) : ((~mask[(i)%8])&t[(i)/8])
#define chr(i) (cs==sizeof(int)?((int*)s)[i]:((unsigned char *)s)[i])
#define isLMS(i) (i>0 && tget(i) && !tget(i-1))

// find the start or end of each bucket
void getBuckets(unsigned char *s, int *bkt, int n, int K, int cs, bool end) {
    int i, sum = 0;
    for (i = 0; i <= K; i++)
        bkt[i] = 0; // clear all buckets
    for (i = 0; i < n; i++)
        bkt[chr(i)]++; // compute the size of each bucket
    for (i = 0; i <= K; i++) {
        sum += bkt[i];
        bkt[i] = end ? sum : sum - bkt[i];
    }
}
// compute SAl
void induceSAl(unsigned char *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) {
    int i, j;
    getBuckets(s, bkt, n, K, cs, end); // find starts of buckets
    for (i = 0; i < n; i++) {
        j = SA[i] - 1;
        if (j >= 0 && !tget(j))
            SA[bkt[chr(j)]++] = j;
    }
}
// compute SAs
void induceSAs(unsigned char *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) {
    int i, j;
    getBuckets(s, bkt, n, K, cs, end); // find ends of buckets
    for (i = n - 1; i >= 0; i--) {
        j = SA[i] - 1;
        if (j >= 0 && tget(j))
            SA[--bkt[chr(j)]] = j;
    }
}

// find the suffix array SA of s[0..n-1] in {1..K}^n
// require s[n-1]=0 (the sentinel!), n>=2
// use a working space (excluding s and SA) of at most 2.25n+O(1) for a constant alphabet
void SA_IS(unsigned char *s, int *SA, int n, int K, int cs) {
    int i, j;
    unsigned char *t = (unsigned char *) malloc(n / 8 + 1); // LS-type array in bits
    // Classify the type of each character
    tset(n-2, 0);
    tset(n-1, 1); // the sentinel must be in s1, important!!!
    for (i = n - 3; i >= 0; i--)
        tset(i, (chr(i)<chr(i+1) || (chr(i)==chr(i+1) && tget(i+1)==1))?1:0);
    // stage 1: reduce the problem by at least 1/2
    // sort all the S-substrings
    int *bkt = (int *) malloc(sizeof(int) * (K + 1)); // bucket array
    getBuckets(s, bkt, n, K, cs, true); // find ends of buckets
    for (i = 0; i < n; i++)
        SA[i] = -1;
    for (i = 1; i < n; i++)
        if (isLMS(i))
            SA[--bkt[chr(i)]] = i;
    induceSAl(t, SA, s, bkt, n, K, cs, false);
    induceSAs(t, SA, s, bkt, n, K, cs, true);
    free(bkt);
    // compact all the sorted substrings into the first n1 items of SA
    // 2*n1 must be not larger than n (proveable)
    int n1 = 0;
    for (i = 0; i < n; i++)
        if (isLMS(SA[i]))
            SA[n1++] = SA[i];
    // find the lexicographic names of all substrings
    for (i = n1; i < n; i++)
        SA[i] = -1; // init the name array buffer
    int name = 0, prev = -1;
    for (i = 0; i < n1; i++) {
        int pos = SA[i];
        bool diff = false;
        for (int d = 0; d < n; d++)
            if (prev == -1 || chr(pos+d) != chr(prev+d) || tget(pos+d) != tget(prev+d)) {
                diff = true;
                break;
            } else if (d > 0 && (isLMS(pos+d) || isLMS(prev+d)))
                break;
        if (diff) {
            name++;
            prev = pos;
        }
        pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
        SA[n1 + pos] = name - 1;
    }
    for (i = n - 1, j = n - 1; i >= n1; i--)
        if (SA[i] >= 0)
            SA[j--] = SA[i];
    // stage 2: solve the reduced problem
    // recurse if names are not yet unique
    int *SA1 = SA, *s1 = SA + n - n1;
    if (name < n1)
        SA_IS((unsigned char*) s1, SA1, n1, name - 1, sizeof(int));
    else
        // generate the suffix array of s1 directly
        for (i = 0; i < n1; i++)
            SA1[s1[i]] = i;
    // stage 3: induce the result for the original problem
    bkt = (int *) malloc(sizeof(int) * (K + 1)); // bucket array
    // put all left-most S characters into their buckets
    getBuckets(s, bkt, n, K, cs, true); // find ends of buckets
    for (i = 1, j = 0; i < n; i++)
        if (isLMS(i))
            s1[j++] = i; // get p1
    for (i = 0; i < n1; i++)
        SA1[i] = s1[SA1[i]]; // get index in s
    for (i = n1; i < n; i++)
        SA[i] = -1; // init SA[n1..n-1]
    for (i = n1 - 1; i >= 0; i--) {
        j = SA[i];
        SA[i] = -1;
        SA[--bkt[chr(j)]] = j;
    }
    induceSAl(t, SA, s, bkt, n, K, cs, false);
    induceSAs(t, SA, s, bkt, n, K, cs, true);
    free(bkt);
    free(t);
}

const int maxn = 1000100;
int sa[maxn];
int lcp[maxn];
int pos[maxn];
unsigned char *s;
int n;

void calc_lcp() {
    for (int i = 0; i < n+1; i++)
        pos[sa[i]] = i;
    for (int i = 0, h = 0; i < n+1; i++) {
        if (pos[i] < n ) {
            for (int j = sa[pos[i] + 1]; s[i + h] == s[j + h]; ++h)
                ;
            lcp[pos[i]] = h;
            if (h > 0)
                --h;
        }
    }
}
/*
 str="abcab" n=5
 SA_IS(str,sa,n+1,256,1)
 calc_lcp()
 sa={5,3,0,4,1,2}
 str.subtring(sa)={"","ab","abcab","b","bcab","cab"}
 lcp={0,2,0,1,0,0}
 pos={2,4,5,1,3,0}
*/

pair<int,int> longest_repeated_substring(int overlap){
    //overlap=1 non-overlapping , overlap=0 overlap allowed
    int maxl=0,maxidx=-1;
    for(int i=1;i<n+1;i++){
        if(lcp[i]>maxl) {
            if(overlap && abs(sa[i]-sa[i-1])<lcp[i]) continue;
            maxl=lcp[i];
            maxidx=sa[i];
        }
    }
    if(maxidx==-1) return make_pair(-1,-1);
    return make_pair(maxidx,maxl);
}
pair<pair<int,int>,int> longest_k_repeated_substring(string str,int k){
    k--;
    for (int i = 0; i < n+1; i++)
        pos[sa[i]] = i;
    int maxl=0,maxidx=-1,rightmostidx=0;
    for (int i = 0, h = 0; i < n+1; i++) {
        if (pos[i] < n +1-k) {
            for (int j = sa[pos[i] + k]; s[i + h] == s[j + h]; ++h)
                ;
            if(h>=maxl){
                if(h>maxl) rightmostidx=sa[pos[i] + k];
                maxl=h;
                maxidx=i;
                if(rightmostidx<sa[pos[i] + k]) rightmostidx=sa[pos[i] + k];
            }
            //cout<<i<<" "<<h<<" "<<str.substr(i,h)<<maxl<<" "<<str.substr(maxidx,maxl)<<" "<<rightmostidx<<endl;

            if (h > 0)
                --h;
        }
    }
    if(maxidx==-1) return make_pair(make_pair(-1,-1),-1);
    return make_pair(make_pair(rightmostidx,maxidx),maxl);
}
pair<pair<int,int>,pair<int,int> > longest_common_substring(string str1,string str2){
    string str=str1+" "+str2;
    s = (unsigned char*) str.c_str();
    n = (int)str.size();
    SA_IS(s, sa, n + 1, 256, 1);
    calc_lcp();
    pair<int,int> p=longest_repeated_substring(0);
    int indx2=sa[pos[p.first]+1];
    //cout<<str.substr(p.first,p.second)<<" "<<str.substr(indx2,p.second)<<endl;
    if((p.first<str1.length()&&indx2<str1.length())||(p.first>str1.length()&&indx2>str1.length()) || str.substr(p.first,p.second)!=str.substr(indx2,p.second)) {
                return make_pair(make_pair(0,0),p);
    }
    return make_pair(p,make_pair(indx2,p.second));
}

pair<int,int> smallest_lex_rotation(string str){
    
    str=str+str;
    s = (unsigned char*) str.c_str();
    
    n = (int)str.size();
    SA_IS(s, sa, n + 1, 256, 1);
    for(int i=1;i<n+1;i++){
        //cout<<str.substr(sa[i])<<" "<<sa[i]<<"\n";
    }
    
    int minval=maxn;
    for(int i=0;i<n+1;i++){
        if(sa[i]<=n/2){
            while(i<n && sa[i]<=n/2 && str.substr(sa[i],n/2)==str.substr(sa[i+1],n/2)){
                if(minval>sa[i]) minval=sa[i];
                //printf("i %d\n",i);
                i++;
            }
            return make_pair(sa[i],n/2);
        }
    }
    
    return make_pair(-1,n/2);
}

long count_distinct_substrings(string str){
    s = (unsigned char*) str.c_str();
    n = (int)str.size();
    SA_IS(s, sa, n + 1, 256, 1);
    calc_lcp();
    long count=0;
    for(int i=1;i<n+1;i++) count+=n-sa[i]-lcp[i];
    return count;
}

pair<int,int> longest_palindromic_substring(string str){
    string revstr=string(str.rbegin(),str.rend());
    return longest_common_substring(str, revstr).first;
}

bool contain(string str, int *sa, string T){
    int a = 0, b = str.length();
    while( b - a > 1 ){
        int c = (a + b ) / 2;
        if ( str.compare(sa[c], T.length(), T) < 0 ) a = c;
        else b = c;
    }
    return str.compare(sa[b], T.length(), T) == 0;
}


int main() {
    string str;
    cin>>str;
    s = (unsigned char*) str.c_str();
    n = (int)str.size();
    SA_IS(s, sa, n + 1, 256, 1);
    int t;
    cin>>t;
    while(t--){
    	string pat;
    	cin>>pat;
    	cout<<contain(str,sa,pat)<<"\n";
    }
}
```