#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

using ll = long long;
using ld = long double;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

class SA_IS {
    public:
        SA_IS() {}

        vector<int> construct(string str) {
            vector<int> s(str.begin(), str.end());
            return construct(s);
        }

        vector<int> construct(vector<int> s, const int k = 128) {
            if (s.size() <= 1) {
                return s.empty() ? (vector<int>){0} : (vector<int>){1, 0};
            }
            s.push_back(0);
            vector<int> bkt(k, 0);
            vector<bool> is_stype(s.size());

            // determine S-type or L-type
            rrep (i, s.size()) {
                bkt[s[i]]++;
                is_stype[i] = (i + 1 == s.size()) || (s[i] < s[i + 1]) || (s[i] == s[i + 1] && is_stype[i + 1]); 
            }
            FOR (i, 1, k) bkt[i] += bkt[i - 1];

            // Induced Sorting with wrong seed
            vector<int> b(bkt);
            
            vector<int> sa(s.size()), is_lms(s.size());
            int lms_cnt = 0;
            FOR (i, 1, s.size()) {
                if (!is_stype[i - 1] && is_stype[i]) {
                    is_lms[i] = 1;
                    sa[--bkt[s[i]]] = i;
                    lms_cnt++;
                }
            }
            
            sa = inducedSort(s, sa, is_stype, b);

            int lms_substr = 1, pre = -1;
            is_lms[sa[0]] = lms_substr++;
            FOR (i, 1, sa.size()) {
                if (!is_lms[sa[i]]) continue;
                if (pre >= 0 && s[pre] == s[sa[i]]) {
                    int k;
                    for (k = 1; s[pre + k] == s[sa[i] + k] && !is_lms[pre + k] && !is_lms[sa[i] + k]; ++k) ;
                    lms_substr -= (s[pre + k] == s[sa[i] + k] && is_lms[pre + k] && is_lms[sa[i] + k]);
                }
                pre = sa[i];
                is_lms[sa[i]] = lms_substr++;
            }

            vector<int> newstr(lms_cnt), rev(lms_cnt);
            int cnt = 0;
            rep (i, s.size()) {
                if (!is_lms[i]) continue;
                newstr[cnt] = is_lms[i];
                rev[cnt] = i;
                cnt++;
            }

            vector<int> sorted_lms = construct(newstr, lms_substr);
            sa.assign(s.size(), 0);
            FOR (i, 1, sorted_lms.size()) {
                int j = rev[sorted_lms[i]];
                sa[bkt[s[j]]++] = j;
            }

            return inducedSort(s, sa, is_stype, b);
        }

        vector<int> inducedSort(const vector<int>& s, const vector<int>&sa, const vector<bool>& is_stype, vector<int> bkt) {
            int n = sa.size();
            vector<int> b(bkt);
            vector<int> res(n);
            res[0] = sa[0];
            rep (i, n) {
                int j = sa[i] - 1, k = res[i] - 1;
                if (j >= 0 && !is_stype[j]) res[b[s[j] - 1]++] = j;
                else if (k >= 0 && !is_stype[k]) res[b[s[k] - 1]++] = k;
            }
            rrep (i, n) {
                int j = res[i] - 1;
                if (j >= 0 && is_stype[j]) res[--bkt[s[j]]] = j;
            }

            return res;
        }

        bool contain(string s, string t, const vector<int>& sa) {
            int l = 0, r = sa.size(), m;
            while (r - l > 1) {
                m = (l + r) / 2;
                if (s.substr(sa[m], t.size()) <= t) l = m;
                else r = m;
            }

            return s.substr(sa[l], t.size()) == t;
        }
};


int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    SA_IS sa = SA_IS();
    string s;
    int q;
    cin >> s >> q;
    vector<int> v = sa.construct(s);
    rep (i, q) {
        string t;
        cin >> t;
        if (sa.contain(s, t, v)) cout << 1 << endl;
        else cout << 0 << endl;
    }
    
    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 <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

using ll = long long;
using ld = long double;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

class SA_IS {
    public:
        SA_IS() {}

        vector<int> construct(string str) {
            vector<int> s(str.begin(), str.end());
            return construct(s);
        }

        vector<int> construct(vector<int> s, const int k = 128) {
            if (s.size() <= 1) {
                return s.empty() ? (vector<int>){0} : (vector<int>){1, 0};
            }
            s.push_back(0);
            vector<int> bkt(k, 0);
            vector<bool> is_stype(s.size());

            // determine S-type or L-type
            rrep (i, s.size()) {
                bkt[s[i]]++;
                is_stype[i] = (i + 1 == s.size()) || (s[i] < s[i + 1]) || (s[i] == s[i + 1] && is_stype[i + 1]); 
            }
            FOR (i, 1, k) bkt[i] += bkt[i - 1];

            // Induced Sorting with wrong seed
            vector<int> b(bkt);
            
            vector<int> sa(s.size()), is_lms(s.size());
            int lms_cnt = 0;
            FOR (i, 1, s.size()) {
                if (!is_stype[i - 1] && is_stype[i]) {
                    is_lms[i] = 1;
                    sa[--bkt[s[i]]] = i;
                    lms_cnt++;
                }
            }
            
            sa = inducedSort(s, sa, is_stype, b);

            int lms_substr = 1, pre = -1;
            is_lms[sa[0]] = lms_substr++;
            FOR (i, 1, sa.size()) {
                if (!is_lms[sa[i]]) continue;
                if (pre >= 0 && s[pre] == s[sa[i]]) {
                    int k;
                    for (k = 1; s[pre + k] == s[sa[i] + k] && !is_lms[pre + k] && !is_lms[sa[i] + k]; ++k) ;
                    lms_substr -= (s[pre + k] == s[sa[i] + k] && is_lms[pre + k] && is_lms[sa[i] + k]);
                }
                pre = sa[i];
                is_lms[sa[i]] = lms_substr++;
            }

            vector<int> newstr(lms_cnt), rev(lms_cnt);
            int cnt = 0;
            rep (i, s.size()) {
                if (!is_lms[i]) continue;
                newstr[cnt] = is_lms[i];
                rev[cnt] = i;
                cnt++;
            }

            vector<int> sorted_lms = construct(newstr, lms_substr);
            sa.assign(s.size(), 0);
            FOR (i, 1, sorted_lms.size()) {
                int j = rev[sorted_lms[i]];
                sa[bkt[s[j]]++] = j;
            }

            return inducedSort(s, sa, is_stype, b);
        }

        vector<int> inducedSort(const vector<int>& s, const vector<int>&sa, const vector<bool>& is_stype, vector<int> bkt) {
            int n = sa.size();
            vector<int> b(bkt);
            vector<int> res(n);
            res[0] = sa[0];
            rep (i, n) {
                int j = sa[i] - 1, k = res[i] - 1;
                if (j >= 0 && !is_stype[j]) res[b[s[j] - 1]++] = j;
                else if (k >= 0 && !is_stype[k]) res[b[s[k] - 1]++] = k;
            }
            rrep (i, n) {
                int j = res[i] - 1;
                if (j >= 0 && is_stype[j]) res[--bkt[s[j]]] = j;
            }

            return res;
        }

        bool contain(string s, string t, const vector<int>& sa) {
            int l = 0, r = sa.size(), m;
            while (r - l > 1) {
                m = (l + r) / 2;
                if (s.substr(sa[m], t.size()) <= t) l = m;
                else r = m;
            }

            return s.substr(sa[l], t.size()) == t;
        }
};


int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    SA_IS sa = SA_IS();
    string s;
    int q;
    cin >> s >> q;
    vector<int> v = sa.construct(s);
    rep (i, q) {
        string t;
        cin >> t;
        if (sa.contain(s, t, v)) cout << 1 << endl;
        else cout << 0 << endl;
    }
    
    return 0;
}



```