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

void induced_sort(vector<int> &vec, int val_range, vector<int> &SA, vector<bool> &sl, vector<int> &lms_idx){
    vector<int> l(val_range, 0), r(val_range, 0);
    for(int c: vec){
        if(c+1 < val_range) ++l[c+1];
        ++r[c];
    }
    partial_sum(l.begin(), l.end(), l.begin());
    partial_sum(r.begin(), r.end(), r.begin());

    fill(SA.begin(), SA.end(), -1);

    for(int i=lms_idx.size()-1; i>=0; --i){
        SA[--r[vec[lms_idx[i]]]] = lms_idx[i];
    }

    for(int i: SA)if(i >= 1 && sl[i-1]){
        SA[l[vec[i-1]]++] = i-1;
    }

    fill(r.begin(), r.end(), 0);
    for(int c: vec) ++r[c];
    partial_sum(r.begin(), r.end(), r.begin());
    for(int k=SA.size()-1, i=SA[k]; k>=1; --k, i=SA[k])if(i >= 1 && !sl[i-1]){
        SA[--r[vec[i-1]]] = i-1;
    }
}

vector<int> SA_IS(vector<int> &vec, int val_range){
    const int n = vec.size();
    vector<int> SA(n), lms_idx;
    vector<bool> sl(n);

    sl[n-1] = false;
    for(int i=n-2; i>=0; --i){
        sl[i] = (vec[i] > vec[i+1] || (vec[i] == vec[i+1] && sl[i+1]));
        if(sl[i] && !sl[i+1]) lms_idx.push_back(i+1);
    }
    reverse(lms_idx.begin(), lms_idx.end());

    induced_sort(vec, val_range, SA, sl, lms_idx);

    vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
    for(int i=0, k=0; i<n; ++i)if(!sl[SA[i]] && SA[i] >= 1 && sl[SA[i]-1]){
        new_lms_idx[k++] = SA[i];
    }

    int cur = 0;
    SA[n-1] = cur;
    for(size_t k=1; k<new_lms_idx.size(); ++k){
        int i = new_lms_idx[k-1], j = new_lms_idx[k];
        if(vec[i] != vec[j]){
            SA[j] = ++cur;
            continue;
        }
        bool flag = false;
        for(int a=i+1, b=j+1; ; ++a, ++b){
            if(vec[a] != vec[b]){
                flag = true;
                break;
            }
            if((!sl[a] && sl[a-1]) || (!sl[b] && sl[b-1])){
                flag = !((!sl[a] && sl[a-1]) && (!sl[b] && sl[b-1]));
                break;
            }
        }
        SA[j] = (flag ? ++cur : cur);
    }
    for(size_t i=0; i<lms_idx.size(); ++i){
        lms_vec[i] = SA[lms_idx[i]];
    }

    if(cur+1 < (int)lms_idx.size()){
        auto lms_SA = SA_IS(lms_vec, cur+1);

        for(size_t i=0; i<lms_idx.size(); ++i){
            new_lms_idx[i] = lms_idx[lms_SA[i]];
        }
    }

    induced_sort(vec, val_range, SA, sl, new_lms_idx);

    return SA;
}

vector<int> suffix_array(string &s){
    s += '$';
    vector<int> vec(s.size());
    for(int i=0; i<s.size(); ++i) vec[i] = s[i];
    auto SA = SA_IS(vec, 128);
    SA.erase(SA.begin());
    return SA;
}

struct BWT{
    int n, width;
    string bwt;
    vector<int> cnt_smaller, SA;
    vector<vector<int>> cnt;

    BWT(string s, int w): n(s.size()+1), width(w){
        SA = suffix_array(s);
        s += '$';
        SA.insert(SA.begin(), n-1);
        bwt.resize(n);
        for(int i=0; i<n; ++i){
            bwt[i] = (SA[i] == 0 ? s[n-1] : s[SA[i]-1]);
        }

        cnt_smaller.resize(128, 0);
        cnt.resize(128);
        for(int i=0; i<128; ++i) cnt[i].resize((n+1)/width+1, 0);
        vector<int> table(128, 0);
        for(int i=0; i<n; ++i){
            if(bwt[i]+1 < 128) ++cnt_smaller[bwt[i]+1];
            ++table[bwt[i]];
            if((i+1)%width == 0){
                for(int c=0; c<128; ++c) cnt[c][(i+1)/width] = table[c];
            }
        }
        partial_sum(cnt_smaller.begin(), cnt_smaller.end(), cnt_smaller.begin());
    }

    int get_cnt(int c, int k){
        int ret = cnt[c][k/width];
        for(int i=k/width*width; i<k; ++i) ret += (bwt[i] == c);
        return ret;
    }

    bool find(string &s){
        int l = 0, r = n;
        for(int i=s.size()-1; i>=0; --i){
            l = cnt_smaller[s[i]] + get_cnt(s[i], l);
            r = cnt_smaller[s[i]] + get_cnt(s[i], r);
            if(l == r) return false;
        }
        return true;
    }
};

int main(){
    string t; int q;
    cin >> t >> q;
    BWT bwt(t, 10);
    while(q--){
        string p;
        cin >> p;
        printf("%d\n", bwt.find(p));
    }
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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

void induced_sort(vector<int> &vec, int val_range, vector<int> &SA, vector<bool> &sl, vector<int> &lms_idx){
    vector<int> l(val_range, 0), r(val_range, 0);
    for(int c: vec){
        if(c+1 < val_range) ++l[c+1];
        ++r[c];
    }
    partial_sum(l.begin(), l.end(), l.begin());
    partial_sum(r.begin(), r.end(), r.begin());

    fill(SA.begin(), SA.end(), -1);

    for(int i=lms_idx.size()-1; i>=0; --i){
        SA[--r[vec[lms_idx[i]]]] = lms_idx[i];
    }

    for(int i: SA)if(i >= 1 && sl[i-1]){
        SA[l[vec[i-1]]++] = i-1;
    }

    fill(r.begin(), r.end(), 0);
    for(int c: vec) ++r[c];
    partial_sum(r.begin(), r.end(), r.begin());
    for(int k=SA.size()-1, i=SA[k]; k>=1; --k, i=SA[k])if(i >= 1 && !sl[i-1]){
        SA[--r[vec[i-1]]] = i-1;
    }
}

vector<int> SA_IS(vector<int> &vec, int val_range){
    const int n = vec.size();
    vector<int> SA(n), lms_idx;
    vector<bool> sl(n);

    sl[n-1] = false;
    for(int i=n-2; i>=0; --i){
        sl[i] = (vec[i] > vec[i+1] || (vec[i] == vec[i+1] && sl[i+1]));
        if(sl[i] && !sl[i+1]) lms_idx.push_back(i+1);
    }
    reverse(lms_idx.begin(), lms_idx.end());

    induced_sort(vec, val_range, SA, sl, lms_idx);

    vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
    for(int i=0, k=0; i<n; ++i)if(!sl[SA[i]] && SA[i] >= 1 && sl[SA[i]-1]){
        new_lms_idx[k++] = SA[i];
    }

    int cur = 0;
    SA[n-1] = cur;
    for(size_t k=1; k<new_lms_idx.size(); ++k){
        int i = new_lms_idx[k-1], j = new_lms_idx[k];
        if(vec[i] != vec[j]){
            SA[j] = ++cur;
            continue;
        }
        bool flag = false;
        for(int a=i+1, b=j+1; ; ++a, ++b){
            if(vec[a] != vec[b]){
                flag = true;
                break;
            }
            if((!sl[a] && sl[a-1]) || (!sl[b] && sl[b-1])){
                flag = !((!sl[a] && sl[a-1]) && (!sl[b] && sl[b-1]));
                break;
            }
        }
        SA[j] = (flag ? ++cur : cur);
    }
    for(size_t i=0; i<lms_idx.size(); ++i){
        lms_vec[i] = SA[lms_idx[i]];
    }

    if(cur+1 < (int)lms_idx.size()){
        auto lms_SA = SA_IS(lms_vec, cur+1);

        for(size_t i=0; i<lms_idx.size(); ++i){
            new_lms_idx[i] = lms_idx[lms_SA[i]];
        }
    }

    induced_sort(vec, val_range, SA, sl, new_lms_idx);

    return SA;
}

vector<int> suffix_array(string &s){
    s += '$';
    vector<int> vec(s.size());
    for(int i=0; i<s.size(); ++i) vec[i] = s[i];
    auto SA = SA_IS(vec, 128);
    SA.erase(SA.begin());
    return SA;
}

struct BWT{
    int n, width;
    string bwt;
    vector<int> cnt_smaller, SA;
    vector<vector<int>> cnt;

    BWT(string s, int w): n(s.size()+1), width(w){
        SA = suffix_array(s);
        s += '$';
        SA.insert(SA.begin(), n-1);
        bwt.resize(n);
        for(int i=0; i<n; ++i){
            bwt[i] = (SA[i] == 0 ? s[n-1] : s[SA[i]-1]);
        }

        cnt_smaller.resize(128, 0);
        cnt.resize(128);
        for(int i=0; i<128; ++i) cnt[i].resize((n+1)/width+1, 0);
        vector<int> table(128, 0);
        for(int i=0; i<n; ++i){
            if(bwt[i]+1 < 128) ++cnt_smaller[bwt[i]+1];
            ++table[bwt[i]];
            if((i+1)%width == 0){
                for(int c=0; c<128; ++c) cnt[c][(i+1)/width] = table[c];
            }
        }
        partial_sum(cnt_smaller.begin(), cnt_smaller.end(), cnt_smaller.begin());
    }

    int get_cnt(int c, int k){
        int ret = cnt[c][k/width];
        for(int i=k/width*width; i<k; ++i) ret += (bwt[i] == c);
        return ret;
    }

    bool find(string &s){
        int l = 0, r = n;
        for(int i=s.size()-1; i>=0; --i){
            l = cnt_smaller[s[i]] + get_cnt(s[i], l);
            r = cnt_smaller[s[i]] + get_cnt(s[i], r);
            if(l == r) return false;
        }
        return true;
    }
};

int main(){
    string t; int q;
    cin >> t >> q;
    BWT bwt(t, 10);
    while(q--){
        string p;
        cin >> p;
        printf("%d\n", bwt.find(p));
    }
}

```