#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

template<class T> inline bool chmin(T &a,T b){
    if (a>b){a=b; return true;}
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if (a<b){a=b; return true;}
    return false;
}

struct SuffixArray{
    string s;
    vector<int> sa,rev;
    SuffixArray(const string &S):s(S){
        int n=s.size();
        s.push_back('$');
        sa.resize(n+1);
        iota(all(sa),0);
        sort(all(sa),[&](int a,int b){
            if (s[a]==s[b]) return a>b;
            return s[a]<s[b];
        });
        vector<int> cs(n+1,0),rs(n+1),cnt(n+1);
        rep(i,n+1) rs[i]=(int)s[i];
        for (int k=1;k<=n;k*=2){
            rep(i,n+1){
                cs[sa[i]]=i;
                if (i&&rs[sa[i-1]]==rs[sa[i]]
                &&sa[i-1]+k<=n&&rs[sa[i-1]+k/2]
                ==rs[sa[i]+k/2]) cs[sa[i]]=cs[sa[i-1]];
            }
            iota(all(cnt),0);
            copy(all(sa),rs.begin());
            rep(i,n+1){
                int sl=rs[i]-k;
                if (sl>=0) sa[cnt[cs[sl]]++]=sl;
            }
            cs.swap(rs);
        }
        rev.resize(n+1);
        rep(i,n+1) rev[sa[i]]=i;
    }
    int operator[](int i){
        return sa[i];
    }
    bool lt_substr(string &t,int si,int ti){
        int sn=s.size(),tn=t.size();
        while(si<sn&&ti<tn){
            if (s[si]<t[ti]) return 1;
            if (s[si]>t[ti]) return 0;
            ++si,++ti;
        }
        return si==sn&&ti<tn;
    }
    int lower_bound(string &t){
        int l=0,r=s.size();
        while(l+1<r){
            int m=(l+r)>>1;
            if (lt_substr(t,sa[m],0)) l=m;
            else r=m;
        }
        return r;
    }
    int upper_bound(string &t){
        ++t.back();
        int res=lower_bound(t);
        --t.back();
        return res;
    }
    int count(string &T){
        return upper_bound(T)-lower_bound(T);
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string T; int Q; cin >> T >> Q;
    SuffixArray SA(T);
    rep(i,Q){
        string P; cin >> P;
        cout << (SA.count(P)>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;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

template<class T> inline bool chmin(T &a,T b){
    if (a>b){a=b; return true;}
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if (a<b){a=b; return true;}
    return false;
}

struct SuffixArray{
    string s;
    vector<int> sa,rev;
    SuffixArray(const string &S):s(S){
        int n=s.size();
        s.push_back('$');
        sa.resize(n+1);
        iota(all(sa),0);
        sort(all(sa),[&](int a,int b){
            if (s[a]==s[b]) return a>b;
            return s[a]<s[b];
        });
        vector<int> cs(n+1,0),rs(n+1),cnt(n+1);
        rep(i,n+1) rs[i]=(int)s[i];
        for (int k=1;k<=n;k*=2){
            rep(i,n+1){
                cs[sa[i]]=i;
                if (i&&rs[sa[i-1]]==rs[sa[i]]
                &&sa[i-1]+k<=n&&rs[sa[i-1]+k/2]
                ==rs[sa[i]+k/2]) cs[sa[i]]=cs[sa[i-1]];
            }
            iota(all(cnt),0);
            copy(all(sa),rs.begin());
            rep(i,n+1){
                int sl=rs[i]-k;
                if (sl>=0) sa[cnt[cs[sl]]++]=sl;
            }
            cs.swap(rs);
        }
        rev.resize(n+1);
        rep(i,n+1) rev[sa[i]]=i;
    }
    int operator[](int i){
        return sa[i];
    }
    bool lt_substr(string &t,int si,int ti){
        int sn=s.size(),tn=t.size();
        while(si<sn&&ti<tn){
            if (s[si]<t[ti]) return 1;
            if (s[si]>t[ti]) return 0;
            ++si,++ti;
        }
        return si==sn&&ti<tn;
    }
    int lower_bound(string &t){
        int l=0,r=s.size();
        while(l+1<r){
            int m=(l+r)>>1;
            if (lt_substr(t,sa[m],0)) l=m;
            else r=m;
        }
        return r;
    }
    int upper_bound(string &t){
        ++t.back();
        int res=lower_bound(t);
        --t.back();
        return res;
    }
    int count(string &T){
        return upper_bound(T)-lower_bound(T);
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string T; int Q; cin >> T >> Q;
    SuffixArray SA(T);
    rep(i,Q){
        string P; cin >> P;
        cout << (SA.count(P)>0) << endl;
    }
}

```