#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string s, t; int q;

struct SuffixArray {
    string str;
    vector<int> sa, rnk;

    SuffixArray (string &str) : str(str) {
        int n = (int)str.size(), itr = 1;

        auto comp = [&](int a, int b) {
            if(rnk[a] != rnk[b]) return rnk[a] < rnk[b];
            return (a + itr < n ? rnk[a + itr] : -1) < (b + itr < n ? rnk[b + itr] : -1);
        };

        for(int i = 0; i < n; ++i) sa.push_back(i), rnk.push_back(str[i]);

        vector<int> tmp(n);
        for(; itr <= n; itr *= 2) {
            sort(sa.begin(), sa.end(), comp);

            tmp[sa[0]] = 0;
            for(int i = 1; i < n; ++i) tmp[sa[i]] = tmp[sa[i-1]] + comp(sa[i-1], sa[i]);
            rnk = tmp;
        }
    }

    bool find(string &t) {
        int ng = -1, ok = (int)str.size()-1;
        while(ok - ng > 1) {
            int mid = (ok + ng) / 2;
            if(str.substr(sa[mid], t.size()) < t) ng = mid;
            else ok = mid;
        }
        return str.substr(sa[ok], t.size()) == t;
    }
};

int main(){
    cin >> s >> q;
    SuffixArray sa(s);

    while(q--) {
        cin >> t;
        cout << sa.find(t) << '\n';
    }
    return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 <vector>
#include <algorithm>
using namespace std;

string s, t; int q;

struct SuffixArray {
    string str;
    vector<int> sa, rnk;

    SuffixArray (string &str) : str(str) {
        int n = (int)str.size(), itr = 1;

        auto comp = [&](int a, int b) {
            if(rnk[a] != rnk[b]) return rnk[a] < rnk[b];
            return (a + itr < n ? rnk[a + itr] : -1) < (b + itr < n ? rnk[b + itr] : -1);
        };

        for(int i = 0; i < n; ++i) sa.push_back(i), rnk.push_back(str[i]);

        vector<int> tmp(n);
        for(; itr <= n; itr *= 2) {
            sort(sa.begin(), sa.end(), comp);

            tmp[sa[0]] = 0;
            for(int i = 1; i < n; ++i) tmp[sa[i]] = tmp[sa[i-1]] + comp(sa[i-1], sa[i]);
            rnk = tmp;
        }
    }

    bool find(string &t) {
        int ng = -1, ok = (int)str.size()-1;
        while(ok - ng > 1) {
            int mid = (ok + ng) / 2;
            if(str.substr(sa[mid], t.size()) < t) ng = mid;
            else ok = mid;
        }
        return str.substr(sa[ok], t.size()) == t;
    }
};

int main(){
    cin >> s >> q;
    SuffixArray sa(s);

    while(q--) {
        cin >> t;
        cout << sa.find(t) << '\n';
    }
    return 0;
}

```