#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

#define size_t int

struct SuffixArray {
    string s;
    size_t n;
    vector<size_t> sarray, rank;
    SuffixArray(string s): s(s), n(s.length()) {
        sarray.assign(n+1, 0);
        rank.assign(n+1, 0);

        for (size_t i=0; i<=n; ++i) {
            sarray[i] = i;
            rank[i] = i<n? s[i]:-1;
        }

        vector<size_t> tmp(n+1);
        for (size_t k=1; k<=n; k<<=1) {
            auto comp=[&, k](size_t i, size_t j)->bool {
                if (rank[i] != rank[j])
                    return rank[i] < rank[j];

                int ri=i+k<=n? rank[i+k]:-1;
                int rj=j+k<=n? rank[j+k]:-1;
                return ri < rj;
            };
            sort(sarray.begin(), sarray.end(), comp);
                
            for (size_t i=1; i<=n; ++i)
                tmp[sarray[i]] = tmp[sarray[i-1]]+comp(sarray[i-1], sarray[i]);

            for (size_t i=0; i<=n; ++i)
                rank[i] = tmp[i];
        }
    }
    bool is_substr(string t) {
        size_t lb=0, ub=s.length();
        while (ub-lb > 1) {
            size_t mid=(lb+ub)>>1;
            (s.compare(sarray[mid], t.length(), t)<0? lb:ub) = mid;
        }
        return !s.compare(sarray[ub], t.length(), t);
    }
};

int main() {
    char buf[1<<20];
    scanf("%s", buf);
    string T(buf);

    SuffixArray sa(T);

    size_t Q;
    scanf("%d", &Q);

    for (size_t i=0; i<Q; ++i) {
        scanf("%s", buf);
        string P(buf);

        printf("%d\n", sa.is_substr(P));
    }

    return 0;
}
### 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 <cstdio>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

#define size_t int

struct SuffixArray {
    string s;
    size_t n;
    vector<size_t> sarray, rank;
    SuffixArray(string s): s(s), n(s.length()) {
        sarray.assign(n+1, 0);
        rank.assign(n+1, 0);

        for (size_t i=0; i<=n; ++i) {
            sarray[i] = i;
            rank[i] = i<n? s[i]:-1;
        }

        vector<size_t> tmp(n+1);
        for (size_t k=1; k<=n; k<<=1) {
            auto comp=[&, k](size_t i, size_t j)->bool {
                if (rank[i] != rank[j])
                    return rank[i] < rank[j];

                int ri=i+k<=n? rank[i+k]:-1;
                int rj=j+k<=n? rank[j+k]:-1;
                return ri < rj;
            };
            sort(sarray.begin(), sarray.end(), comp);
                
            for (size_t i=1; i<=n; ++i)
                tmp[sarray[i]] = tmp[sarray[i-1]]+comp(sarray[i-1], sarray[i]);

            for (size_t i=0; i<=n; ++i)
                rank[i] = tmp[i];
        }
    }
    bool is_substr(string t) {
        size_t lb=0, ub=s.length();
        while (ub-lb > 1) {
            size_t mid=(lb+ub)>>1;
            (s.compare(sarray[mid], t.length(), t)<0? lb:ub) = mid;
        }
        return !s.compare(sarray[ub], t.length(), t);
    }
};

int main() {
    char buf[1<<20];
    scanf("%s", buf);
    string T(buf);

    SuffixArray sa(T);

    size_t Q;
    scanf("%d", &Q);

    for (size_t i=0; i<Q; ++i) {
        scanf("%s", buf);
        string P(buf);

        printf("%d\n", sa.is_substr(P));
    }

    return 0;
}
```