#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

#define fi(x) get<0>(x)
#define se(x) get<1>(x)

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;
typedef vector<pll> vpl;

string t;
string p;
lli q;

vll sa;
vll tmp;
vll rnk_;
vll rnk;



int main(){
    cin >> t;
    sa = vll(t.size());rnk = vll(t.size()),rnk_ = vll(t.size());tmp = vll(t.size());
    for(lli i = 0;i < t.size();i++) sa[i] = i;
    for(lli i = 0;i < t.size();i++) rnk[i] = t[i];
    sort(sa.begin(),sa.end(),[](lli a,lli b){
        return rnk[a] < rnk[b];
    });
    for(lli k = 1;k < 2*t.size();k *= 2){
        lli from = 0;
        lli to = 0;
        do{
            from = to;
            while(to < rnk.size() && rnk[sa[from]] == rnk[sa[to]]) to++;
            for(lli i = from;i < to;i++) rnk_[sa[i]] = sa[i]+k < rnk.size() ? rnk[sa[i]+k] : -1;
            sort(sa.begin()+from,sa.begin()+to,[](lli a,lli b){
                return rnk_[a] < rnk_[b];
            });
        }while(to < sa.size());
        tmp[sa[0]] = 0;
        for(lli i = 1;i < sa.size();i++){
            lli c = 1;
            if(rnk[sa[i-1]] == rnk[sa[i]] && rnk_[sa[i-1]] == rnk_[sa[i]]) c = 0;
            tmp[sa[i]] = tmp[sa[i-1]] + c;

        }
        for(lli i = 0;i < sa.size();i++){
            rnk[sa[i]] = tmp[sa[i]];
        }
    }
    sort(sa.begin(),sa.end(),[](lli a,lli b){
        return rnk[a] < rnk[b];
    });
    //for(lli i = 0;i < sa.size();i++) cout << sa[i] << endl;
    /*
    for(lli i = 0;i < sa.size();i++){
        for(lli j = sa[i];j < t.size();j++) cout << t[j];
        cout << endl;
    }
    */
    
    cin >> q;
    for(lli i = 0;i < q;i++){
        cin >> p;
        auto from = sa.begin();
        auto to = sa.end();
        for(lli i = 0;i < p.size();i++){
            from = lower_bound(from,to,p[i],[i](lli x,char c){
                if(x+i >= t.size()) return false;
                return t[x+i] < c;
            });
            to = lower_bound(from,to,p[i],[i](lli x,char c){
                if(x+i >= t.size()) return false;
                return t[x+i] < c+1;
            });
            //cout << from-sa.begin() << " " << to-sa.begin() << endl;
        }
        if(to-from > 0) cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}
### Prompt

Your task is to create a Cpp solution 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 <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

#define fi(x) get<0>(x)
#define se(x) get<1>(x)

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;
typedef vector<pll> vpl;

string t;
string p;
lli q;

vll sa;
vll tmp;
vll rnk_;
vll rnk;



int main(){
    cin >> t;
    sa = vll(t.size());rnk = vll(t.size()),rnk_ = vll(t.size());tmp = vll(t.size());
    for(lli i = 0;i < t.size();i++) sa[i] = i;
    for(lli i = 0;i < t.size();i++) rnk[i] = t[i];
    sort(sa.begin(),sa.end(),[](lli a,lli b){
        return rnk[a] < rnk[b];
    });
    for(lli k = 1;k < 2*t.size();k *= 2){
        lli from = 0;
        lli to = 0;
        do{
            from = to;
            while(to < rnk.size() && rnk[sa[from]] == rnk[sa[to]]) to++;
            for(lli i = from;i < to;i++) rnk_[sa[i]] = sa[i]+k < rnk.size() ? rnk[sa[i]+k] : -1;
            sort(sa.begin()+from,sa.begin()+to,[](lli a,lli b){
                return rnk_[a] < rnk_[b];
            });
        }while(to < sa.size());
        tmp[sa[0]] = 0;
        for(lli i = 1;i < sa.size();i++){
            lli c = 1;
            if(rnk[sa[i-1]] == rnk[sa[i]] && rnk_[sa[i-1]] == rnk_[sa[i]]) c = 0;
            tmp[sa[i]] = tmp[sa[i-1]] + c;

        }
        for(lli i = 0;i < sa.size();i++){
            rnk[sa[i]] = tmp[sa[i]];
        }
    }
    sort(sa.begin(),sa.end(),[](lli a,lli b){
        return rnk[a] < rnk[b];
    });
    //for(lli i = 0;i < sa.size();i++) cout << sa[i] << endl;
    /*
    for(lli i = 0;i < sa.size();i++){
        for(lli j = sa[i];j < t.size();j++) cout << t[j];
        cout << endl;
    }
    */
    
    cin >> q;
    for(lli i = 0;i < q;i++){
        cin >> p;
        auto from = sa.begin();
        auto to = sa.end();
        for(lli i = 0;i < p.size();i++){
            from = lower_bound(from,to,p[i],[i](lli x,char c){
                if(x+i >= t.size()) return false;
                return t[x+i] < c;
            });
            to = lower_bound(from,to,p[i],[i](lli x,char c){
                if(x+i >= t.size()) return false;
                return t[x+i] < c+1;
            });
            //cout << from-sa.begin() << " " << to-sa.begin() << endl;
        }
        if(to-from > 0) cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}
```