
#include <bits/stdc++.h>
using namespace std;

struct suffix_array{
    int n;
    vector <int> x;
    suffix_array(const char *s) : n(strlen(s)),x(n){
        vector<int> r(n),t(n);
        for (int i = 0; i < n; ++i) r[x[i] = i] = s[i];
        for (int h = 1; t[n-1] != n-1 ; h *= 2) {
            auto cmp = [&](int i,int j){
                if(r[i] != r[j]) return r[i] < r[j];
                return i + h < n && j + h < n ? r[i+h] < r[j+h] : i >j;
            };
            sort(x.begin(),x.end(),cmp);
            for (int i = 0; i + 1 < n ; ++i)  t[i + 1] = t[i] + cmp(x[i],x[i+1]);
            for (int i = 0; i < n; ++i)  r[x[i]] = t[i];
        }
    }
    int operator[] (int i) const {return x[i];}
};

bool contain(const string &S, int *sa, const string &T) {
    int lb = -1, ub = S.size() - 1;
    while(ub -lb > 1){
        int mid = (lb + ub )/ 2;
        if(S.compare(sa[mid], T.size(), T) >= 0) ub = mid;
        else lb = mid;
    }
    return S.compare(sa[ub], T.size(), T) == 0;
}

signed main(){
    ios::sync_with_stdio(false);
    string T; cin >> T;
    int Q; cin >> Q;
    suffix_array sary(T.c_str());
    while(Q--){
        string P; cin >> P;
        cout << (contain(T,sary.x.data(),P) ? 1 : 0) << endl;
    }
}
### Prompt

Generate 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 <bits/stdc++.h>
using namespace std;

struct suffix_array{
    int n;
    vector <int> x;
    suffix_array(const char *s) : n(strlen(s)),x(n){
        vector<int> r(n),t(n);
        for (int i = 0; i < n; ++i) r[x[i] = i] = s[i];
        for (int h = 1; t[n-1] != n-1 ; h *= 2) {
            auto cmp = [&](int i,int j){
                if(r[i] != r[j]) return r[i] < r[j];
                return i + h < n && j + h < n ? r[i+h] < r[j+h] : i >j;
            };
            sort(x.begin(),x.end(),cmp);
            for (int i = 0; i + 1 < n ; ++i)  t[i + 1] = t[i] + cmp(x[i],x[i+1]);
            for (int i = 0; i < n; ++i)  r[x[i]] = t[i];
        }
    }
    int operator[] (int i) const {return x[i];}
};

bool contain(const string &S, int *sa, const string &T) {
    int lb = -1, ub = S.size() - 1;
    while(ub -lb > 1){
        int mid = (lb + ub )/ 2;
        if(S.compare(sa[mid], T.size(), T) >= 0) ub = mid;
        else lb = mid;
    }
    return S.compare(sa[ub], T.size(), T) == 0;
}

signed main(){
    ios::sync_with_stdio(false);
    string T; cin >> T;
    int Q; cin >> Q;
    suffix_array sary(T.c_str());
    while(Q--){
        string P; cin >> P;
        cout << (contain(T,sary.x.data(),P) ? 1 : 0) << endl;
    }
}
```