#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

class SA_IS
{
private:
    using byte = unsigned char;
    byte mask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
    #define tget(i) !!(t[(i)>>3]&mask[(i)&7])
    #define tset(i, b) t[(i)>>3]=(b) ? (mask[(i)&7]|t[(i)>>3]) : ((~mask[(i)&7])&t[(i)>>3])
    #define chr(i) (cs==sizeof(int)?((int*)s)[i]:((byte *)s)[i])
    #define isLMS(i) (i>0 && tget(i) && !tget(i-1))
    void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
        fill(bkt, bkt + K + 1, 0);
        for(int i = 0; i < n; i++){
            bkt[chr(i)]++;
        }
        for(int i = 0,tmp = 0; i < K+1; i++){
            tmp += bkt[i];
            bkt[i] = end ? tmp : tmp - bkt[i];
        }
    }
    void induceSAl(byte *t, byte *s, int *bkt, int n, int K, int cs){
        getBuckets(s, bkt, n, K, cs, false);
        for(int i = 0; i < n; i++){
            if(sa[i]>0 && !tget(sa[i]-1)){
                sa[bkt[chr(sa[i]-1)]++] = sa[i]-1;
            }
        }
    }
    void induceSAs(byte *t, byte *s, int *bkt, int n, int K, int cs){
        getBuckets(s, bkt, n, K, cs, true);
        for(int i = n-1; i >= 0; i--){
            if(sa[i] > 0 && tget(sa[i]-1)){
                sa[--bkt[chr(sa[i]-1)]] = sa[i]-1;
            }
        }
    }
    void solve(byte *s, int n, int K=128, int cs=1){
        byte t[(n >> 3)+1];
        int bkt[K+1], n1 = 0, name = 0;
        tset(n-2, 0), tset(n-1, 1);
        for(int i = n - 3; i >=0; i--){
            tset(i, (chr(i)<chr(i+1) || (chr(i)==chr(i+1) && tget(i+1))));
        }
        getBuckets(s, bkt, n, K, cs);
        fill(sa, sa+n, -1);
        for(int i = 1; i < n; i++){
            if(isLMS(i)){
                sa[--bkt[chr(i)]] = i;
            }
        }
        induceSAl(t, s, bkt, n, K, cs);
        induceSAs(t, s, bkt, n, K, cs);
        for(int i = 0; i < n; i++){
            if(isLMS(sa[i])){
                sa[n1++] = sa[i];
            }
        }
        fill(sa + n1, sa + n, -1);
        for(int i = 0, tmp = -1; i < n1; i++){
            int pos = sa[i], diff = false;
            for(int d = 0; d < n && !diff; d++){
                diff = chr(pos+d) != chr(tmp+d) || tget(pos+d) != tget(tmp+d);
                if(!diff && d && (isLMS(pos+d) || isLMS(tmp+d))) break;
            }
            if(diff){
                name++, tmp = pos;
            }
            sa[n1+((pos - (pos & 1)) >> 1)] = name - 1;
        }
        int* s1 = sa + n - n1;
        for(int i = n - 1,j = n - 1; i >= n1; i--){
            if(sa[i] >= 0){
                sa[j--] = sa[i];
            }
        }
        if(name < n1){
            solve((byte*)s1, n1, name - 1, sizeof(int));
        }else{
            for(int i = 0; i < n1; i++){
                sa[s1[i]] = i;
            }
        }
        getBuckets(s, bkt, n, K, cs);
        for(int i = 1, j = 0; i < n; i++){
            if(isLMS(i)){
                s1[j++] = i;
            }
        }
        for(int i = 0; i < n1; i++){
            sa[i] = s1[sa[i]];
        }
        fill(sa + n1, sa + n, -1);
        for(int i = n1 - 1; i >= 0; i--){
          int tmp = sa[i];
          sa[i] = -1, sa[--bkt[chr(tmp)]] = tmp;
        }
        induceSAl(t, s, bkt, n, K, cs);
        induceSAs(t, s, bkt, n, K, cs);
    }
public:
    bool contain(const string& T){
        int a = 0, b = sz;
        while(b - a > 1){
            int c = (a + b) / 2;
            if(CS.compare(sa[c], T.length(), T) < 0){
                a = c;
            }else{
                b = c;
            }
        }
        return CS.compare(sa[b], T.length(), T) == 0;
    }
    string CS;
    byte* S;
    int sz;
    int* sa;
    SA_IS(string& arg){
        CS = arg;
        sz = (int)arg.size();
        sa = new int[sz+1];
        S = (byte*)arg.c_str();
        solve(S, sz+1);
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    SA_IS sa(s);
    int n;
    cin >> n;
    rep(i,n){
        string t;
        cin >> t;
        cout << sa.contain(t) << "\n";
    }
    return 0;
}


### 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>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

class SA_IS
{
private:
    using byte = unsigned char;
    byte mask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
    #define tget(i) !!(t[(i)>>3]&mask[(i)&7])
    #define tset(i, b) t[(i)>>3]=(b) ? (mask[(i)&7]|t[(i)>>3]) : ((~mask[(i)&7])&t[(i)>>3])
    #define chr(i) (cs==sizeof(int)?((int*)s)[i]:((byte *)s)[i])
    #define isLMS(i) (i>0 && tget(i) && !tget(i-1))
    void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
        fill(bkt, bkt + K + 1, 0);
        for(int i = 0; i < n; i++){
            bkt[chr(i)]++;
        }
        for(int i = 0,tmp = 0; i < K+1; i++){
            tmp += bkt[i];
            bkt[i] = end ? tmp : tmp - bkt[i];
        }
    }
    void induceSAl(byte *t, byte *s, int *bkt, int n, int K, int cs){
        getBuckets(s, bkt, n, K, cs, false);
        for(int i = 0; i < n; i++){
            if(sa[i]>0 && !tget(sa[i]-1)){
                sa[bkt[chr(sa[i]-1)]++] = sa[i]-1;
            }
        }
    }
    void induceSAs(byte *t, byte *s, int *bkt, int n, int K, int cs){
        getBuckets(s, bkt, n, K, cs, true);
        for(int i = n-1; i >= 0; i--){
            if(sa[i] > 0 && tget(sa[i]-1)){
                sa[--bkt[chr(sa[i]-1)]] = sa[i]-1;
            }
        }
    }
    void solve(byte *s, int n, int K=128, int cs=1){
        byte t[(n >> 3)+1];
        int bkt[K+1], n1 = 0, name = 0;
        tset(n-2, 0), tset(n-1, 1);
        for(int i = n - 3; i >=0; i--){
            tset(i, (chr(i)<chr(i+1) || (chr(i)==chr(i+1) && tget(i+1))));
        }
        getBuckets(s, bkt, n, K, cs);
        fill(sa, sa+n, -1);
        for(int i = 1; i < n; i++){
            if(isLMS(i)){
                sa[--bkt[chr(i)]] = i;
            }
        }
        induceSAl(t, s, bkt, n, K, cs);
        induceSAs(t, s, bkt, n, K, cs);
        for(int i = 0; i < n; i++){
            if(isLMS(sa[i])){
                sa[n1++] = sa[i];
            }
        }
        fill(sa + n1, sa + n, -1);
        for(int i = 0, tmp = -1; i < n1; i++){
            int pos = sa[i], diff = false;
            for(int d = 0; d < n && !diff; d++){
                diff = chr(pos+d) != chr(tmp+d) || tget(pos+d) != tget(tmp+d);
                if(!diff && d && (isLMS(pos+d) || isLMS(tmp+d))) break;
            }
            if(diff){
                name++, tmp = pos;
            }
            sa[n1+((pos - (pos & 1)) >> 1)] = name - 1;
        }
        int* s1 = sa + n - n1;
        for(int i = n - 1,j = n - 1; i >= n1; i--){
            if(sa[i] >= 0){
                sa[j--] = sa[i];
            }
        }
        if(name < n1){
            solve((byte*)s1, n1, name - 1, sizeof(int));
        }else{
            for(int i = 0; i < n1; i++){
                sa[s1[i]] = i;
            }
        }
        getBuckets(s, bkt, n, K, cs);
        for(int i = 1, j = 0; i < n; i++){
            if(isLMS(i)){
                s1[j++] = i;
            }
        }
        for(int i = 0; i < n1; i++){
            sa[i] = s1[sa[i]];
        }
        fill(sa + n1, sa + n, -1);
        for(int i = n1 - 1; i >= 0; i--){
          int tmp = sa[i];
          sa[i] = -1, sa[--bkt[chr(tmp)]] = tmp;
        }
        induceSAl(t, s, bkt, n, K, cs);
        induceSAs(t, s, bkt, n, K, cs);
    }
public:
    bool contain(const string& T){
        int a = 0, b = sz;
        while(b - a > 1){
            int c = (a + b) / 2;
            if(CS.compare(sa[c], T.length(), T) < 0){
                a = c;
            }else{
                b = c;
            }
        }
        return CS.compare(sa[b], T.length(), T) == 0;
    }
    string CS;
    byte* S;
    int sz;
    int* sa;
    SA_IS(string& arg){
        CS = arg;
        sz = (int)arg.size();
        sa = new int[sz+1];
        S = (byte*)arg.c_str();
        solve(S, sz+1);
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    SA_IS sa(s);
    int n;
    cin >> n;
    rep(i,n){
        string t;
        cin >> t;
        cout << sa.contain(t) << "\n";
    }
    return 0;
}


```