#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <cassert>
using namespace std;

const int ALPH = 256;
struct SuffixArray {
private:
    string s;
    vector<int> rec, cnt;
    int len, cnt_size;
public:
    SuffixArray(string s_) : s(s_) {
        s += "$"; // 辞書順で最も小さいダミー文字
        len = s.length();
        cnt_size = max(ALPH, len); cnt.resize(cnt_size);
        rec = getArray();
    }

    void dump_array(vector<int> &indices, vector<int> &classes) {
        fprintf(stderr, "# debug\n");
        fprintf(stderr, "# indices:");
        for(int i=0; i<len; i++) fprintf(stderr, " %d", indices[i]);
        fprintf(stderr, "\n");
        fprintf(stderr, "# classes:");
        for(int i=0; i<len; i++) fprintf(stderr, " %d", classes[i]);
        fprintf(stderr, "\n");
    }
    
    vector<int> getArray() {
        vector<int> indices(len), prev_idx(len);
        vector<int> classes(len), prev_cls(len);
        vector<int> tmp_val(len);

        // k == 0 はカウントソートのみ
        for(int i=0; i<len; i++) {
            cnt[ s[i] ]++;
        }
        for(int i=1; i<cnt_size; i++) {
            cnt[i] += cnt[i-1];
        }
        for(int i=len-1; i>=0; i--) {
            indices[ --cnt[ s[i] ] ] = i;
        }
        for(int i=1; i<len; i++) {
            int pena = (s[ indices[i] ] != s[ indices[i-1] ]);
            classes[ indices[i] ] = classes[ indices[i-1] ] + pena;
        }
        // dump_array(indices, classes);
        
        for(int k=0; (1 << k) < len; k++) {
            swap(indices, prev_idx);
            swap(classes, prev_cls);
            for(int i=0; i<len; i++) {
                // 後半だけソート済みにしたものを indices に代入
                prev_idx[i] = prev_idx[i] - (1 << k);
                if(prev_idx[i] < 0) prev_idx[i] += len;
                tmp_val[i] = prev_cls[ prev_idx[i] ];
            }

            // 前半についてカウントソート
            fill(cnt.begin(), cnt.end(), (int)0);
            for(int i=0; i<len; i++) {
                cnt[ tmp_val[i] ]++;
            }
            for(int i=1; i<cnt_size; i++) {
                cnt[i] += cnt[i-1];
            }
            for(int i=len-1; i>=0; i--) {
                indices[ --cnt[ tmp_val[i] ] ] = prev_idx[i];
            }
            classes[ indices[0] ] = 0;
            for(int i=1; i<len; i++) {
                int shift = (1 << k);
                pair<int, int> pre(prev_cls[ indices[i-1] ], prev_cls[ (indices[i-1] + shift) % len ]);
                pair<int, int> cur(prev_cls[ indices[i  ] ], prev_cls[ (indices[i  ] + shift) % len ]);
                int pena = (pre != cur);
                classes[ indices[i] ] = classes[ indices[i-1] ] + pena;
            }   
            // dump_array(indices, classes);
        }
        return indices;
    }

    int size() {
        return rec.size();
    }
    int get(int idx) {
        assert(0 <= idx and idx < size());
        return rec[idx];
    }
    // パターン文字列 p は、idx 番目に小さい接尾辞に比べて大きいか？
    bool is_greater(string &p, int idx) {
        idx = get(idx);
        int N = size(), M = p.size(), x, y;
        for(x=idx, y=0; x<N and y<M; x++, y++) {
            if(s[x] < p[y]) return true;
            if(s[x] > p[y]) return false;
        }
        return x >= N and y < M;
    }
};

int search_by_sa(SuffixArray &sa, string &p) {
    int N = sa.size(), ansL, ansR;

    int lb = 0, ub = N;
    while(ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if(sa.is_greater(p, mid)) lb = mid;
        else ub = mid;
    }
    ansL = ub;

    p.back()++;
    
    lb = 0, ub = N;
    while(ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if(sa.is_greater(p, mid)) lb = mid;
        else ub = mid;
    }
    ansR = ub;
    p.back()--;

    return ansR - ansL;
}

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

    /*
    for(int i=0; i<=s.length(); i++) {
        cout << s.substr(sa.get(i)) << endl;
    }
    */

    int N; cin >> N;
    for(int i=0; i<N; i++) {
        string p; cin >> p;
        if(search_by_sa(sa, p) > 0) {
            cout << 1 << endl;
        }
        else {
            cout << 0 << endl;
        }
    }
    return 0;
}


### Prompt

Your challenge is to write 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 <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <cassert>
using namespace std;

const int ALPH = 256;
struct SuffixArray {
private:
    string s;
    vector<int> rec, cnt;
    int len, cnt_size;
public:
    SuffixArray(string s_) : s(s_) {
        s += "$"; // 辞書順で最も小さいダミー文字
        len = s.length();
        cnt_size = max(ALPH, len); cnt.resize(cnt_size);
        rec = getArray();
    }

    void dump_array(vector<int> &indices, vector<int> &classes) {
        fprintf(stderr, "# debug\n");
        fprintf(stderr, "# indices:");
        for(int i=0; i<len; i++) fprintf(stderr, " %d", indices[i]);
        fprintf(stderr, "\n");
        fprintf(stderr, "# classes:");
        for(int i=0; i<len; i++) fprintf(stderr, " %d", classes[i]);
        fprintf(stderr, "\n");
    }
    
    vector<int> getArray() {
        vector<int> indices(len), prev_idx(len);
        vector<int> classes(len), prev_cls(len);
        vector<int> tmp_val(len);

        // k == 0 はカウントソートのみ
        for(int i=0; i<len; i++) {
            cnt[ s[i] ]++;
        }
        for(int i=1; i<cnt_size; i++) {
            cnt[i] += cnt[i-1];
        }
        for(int i=len-1; i>=0; i--) {
            indices[ --cnt[ s[i] ] ] = i;
        }
        for(int i=1; i<len; i++) {
            int pena = (s[ indices[i] ] != s[ indices[i-1] ]);
            classes[ indices[i] ] = classes[ indices[i-1] ] + pena;
        }
        // dump_array(indices, classes);
        
        for(int k=0; (1 << k) < len; k++) {
            swap(indices, prev_idx);
            swap(classes, prev_cls);
            for(int i=0; i<len; i++) {
                // 後半だけソート済みにしたものを indices に代入
                prev_idx[i] = prev_idx[i] - (1 << k);
                if(prev_idx[i] < 0) prev_idx[i] += len;
                tmp_val[i] = prev_cls[ prev_idx[i] ];
            }

            // 前半についてカウントソート
            fill(cnt.begin(), cnt.end(), (int)0);
            for(int i=0; i<len; i++) {
                cnt[ tmp_val[i] ]++;
            }
            for(int i=1; i<cnt_size; i++) {
                cnt[i] += cnt[i-1];
            }
            for(int i=len-1; i>=0; i--) {
                indices[ --cnt[ tmp_val[i] ] ] = prev_idx[i];
            }
            classes[ indices[0] ] = 0;
            for(int i=1; i<len; i++) {
                int shift = (1 << k);
                pair<int, int> pre(prev_cls[ indices[i-1] ], prev_cls[ (indices[i-1] + shift) % len ]);
                pair<int, int> cur(prev_cls[ indices[i  ] ], prev_cls[ (indices[i  ] + shift) % len ]);
                int pena = (pre != cur);
                classes[ indices[i] ] = classes[ indices[i-1] ] + pena;
            }   
            // dump_array(indices, classes);
        }
        return indices;
    }

    int size() {
        return rec.size();
    }
    int get(int idx) {
        assert(0 <= idx and idx < size());
        return rec[idx];
    }
    // パターン文字列 p は、idx 番目に小さい接尾辞に比べて大きいか？
    bool is_greater(string &p, int idx) {
        idx = get(idx);
        int N = size(), M = p.size(), x, y;
        for(x=idx, y=0; x<N and y<M; x++, y++) {
            if(s[x] < p[y]) return true;
            if(s[x] > p[y]) return false;
        }
        return x >= N and y < M;
    }
};

int search_by_sa(SuffixArray &sa, string &p) {
    int N = sa.size(), ansL, ansR;

    int lb = 0, ub = N;
    while(ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if(sa.is_greater(p, mid)) lb = mid;
        else ub = mid;
    }
    ansL = ub;

    p.back()++;
    
    lb = 0, ub = N;
    while(ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if(sa.is_greater(p, mid)) lb = mid;
        else ub = mid;
    }
    ansR = ub;
    p.back()--;

    return ansR - ansL;
}

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

    /*
    for(int i=0; i<=s.length(); i++) {
        cout << s.substr(sa.get(i)) << endl;
    }
    */

    int N; cin >> N;
    for(int i=0; i<N; i++) {
        string p; cin >> p;
        if(search_by_sa(sa, p) > 0) {
            cout << 1 << endl;
        }
        else {
            cout << 0 << endl;
        }
    }
    return 0;
}


```