#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;

vector<int> SuffixArray;

vector<int> SA_IS(vector<int> str, int var) {
    if(str.size() == 1) {
        vector<int> ret(1,0);
        return ret;
    }
    str.push_back(0);
    int si = str.size();
    vector<int> st(var, 0), en(var, 0);
    vector<int> SL(si, 0); //s..0, l..1
    vector<int> SA(si, -1);
    vector<int> LMS;
    vector<int> is_LMS(si, -1);
    rep(i,str.size()) en[str[i]]++;
    for(int i = 1; i < var; i++) en[i] += en[i-1];
    for(int i = 1; i < var; i++) st[i] = en[i-1];
    SL[str.size()-1] = 0;
    for(int i = str.size()-2; i >= 0; i--) {
        if(str[i] == str[i+1]) {
            SL[i] = SL[i+1];
            continue;
        }
        if(str[i] > str[i+1]) SL[i] = 1;
        else SL[i] = 0;
    }
    for(int i = 1; i < str.size(); i++) {
        if(SL[i] == 0 && SL[i-1] == 1) {
            SA[--en[str[i]]] = i;
            LMS.push_back(i);
            is_LMS[i] = 1;
        }
    }
    rep(i,var-1) en[i] = st[i+1];
    en[var-1] = str.size();

    rep(i,str.size()) if(SA[i] > 0 && SL[SA[i]-1] == 1) { SA[st[str[SA[i]-1]]++] = SA[i]-1; }
    st[0] = 0;
    for(int i = 1; i < var; i++) st[i] = en[i-1];

    for(int i = 1; i < str.size(); i++) if(SA[i] != -1 && SL[SA[i]] == 0) { SA[i] = -1; }

    for(int i = str.size()-1; i >= 1; i--) if(SA[i] > 0 && SL[SA[i]-1] == 0) { SA[--en[str[SA[i]-1]]] = SA[i]-1; }
    rep(i,var-1) en[i] = st[i+1];
    en[var-1] = str.size();

    int counter = 0;
    vector<int> pre_sa, new_sa;
    rep(i,SA.size()) if(is_LMS[SA[i]] != -1) {
        is_LMS[SA[i]] = ++counter;

        new_sa.clear();
        for(int j = SA[i]; j < SA.size(); j++) {
            new_sa.push_back(str[j]);
            if(j != SA[i] && is_LMS[j] != -1) {
                break;
            }
        }
        if(pre_sa == new_sa) {
            is_LMS[SA[i]] = --counter;
        }
        pre_sa = new_sa;
    }

    vector<int> new_str;
    vector<int> rev((int)LMS.size()+1, 0);
    counter = 0;
    rep(i,is_LMS.size()) {
        if(is_LMS[i] != -1) {
            new_str.push_back(is_LMS[i]);
            rev[counter++] = i;
        }
    }
    vector<int> rec = SA_IS(new_str, new_str.size()+1);

    rep(i,SA.size()) SA[i] = -1;

    for(int i = rec.size()-1; i >= 0; i--) { SA[--en[str[rev[rec[i]]]]] = rev[rec[i]]; }
    rep(i,var-1) en[i] = st[i+1];
    en[var-1] = str.size();

    rep(i,str.size()) if(SA[i] > 0 && SL[SA[i]-1] == 1) { SA[st[str[SA[i]-1]]++] = SA[i]-1; }

    for(int i = 1; i < str.size(); i++) if(SA[i] != -1 && SL[SA[i]] == 0) { SA[i] = -1; }

    for(int i = str.size()-1; i >= 1; i--) if(SA[i] > 0 && SL[SA[i]-1] == 0) { SA[--en[str[SA[i]-1]]] = SA[i]-1; }

    SA.erase(SA.begin());
    return SA;
}

string t;
int q;

bool it_substr(int saidx, const vector<int> &text, const vector<int> &pt) {
  int len = pt.size();
  int n = t.size();
  len = min(len, n - SuffixArray[saidx]);
  int st = SuffixArray[saidx];
  int d = 0;
  rep(i, len) {
    d++;
    if (text[st+i] < pt[i]) return true;
    else if (text[st+i] > pt[i]) return false;
  }
  if (st + d < n) {
    return false;
  }
  else {
    if (d < (int)pt.size()) return true;
    else return false;
  }
}

bool match(const vector<int> &text, const vector<int> &pt) {
    int n = t.size();
    int l = -1, r = n;
    while (r - l > 1) {
        int m = (r + l) / 2;
        if (it_substr(m, text, pt)) l = m;
        else r = m;
    }
    if (r == n) return false;
    //cerr << r << endl;
    int st = SuffixArray[r];
    if (st + (int)pt.size() > n) return false;
    rep(i, pt.size()) {
      if (pt[i] != text[st+i]) return false;
    }
    return true;
}

map<char, int> trans;
int trans_counter = 0;

vector<int> string_to_nums(string& s) {
  rep(i, s.size()) {
    if (trans.find(s[i]) != trans.end()) continue;
    trans[s[i]] = ++trans_counter;
  }
  vector<int> ret;
  rep(i, s.size()) {
    ret.push_back(trans[s[i]]);
  }
  return ret;
}


int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  cin >> t;
  cin >> q;
  vector<int> words = string_to_nums(t);
  SuffixArray = SA_IS(words, 256);
  rep(i, q) {
    string p;
    cin >> p;
    vector<int> pwords = string_to_nums(p);
    if (match(words, pwords)) cout << 1 << endl;
    else cout << 0 << endl;
  }
}


### 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 <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;

vector<int> SuffixArray;

vector<int> SA_IS(vector<int> str, int var) {
    if(str.size() == 1) {
        vector<int> ret(1,0);
        return ret;
    }
    str.push_back(0);
    int si = str.size();
    vector<int> st(var, 0), en(var, 0);
    vector<int> SL(si, 0); //s..0, l..1
    vector<int> SA(si, -1);
    vector<int> LMS;
    vector<int> is_LMS(si, -1);
    rep(i,str.size()) en[str[i]]++;
    for(int i = 1; i < var; i++) en[i] += en[i-1];
    for(int i = 1; i < var; i++) st[i] = en[i-1];
    SL[str.size()-1] = 0;
    for(int i = str.size()-2; i >= 0; i--) {
        if(str[i] == str[i+1]) {
            SL[i] = SL[i+1];
            continue;
        }
        if(str[i] > str[i+1]) SL[i] = 1;
        else SL[i] = 0;
    }
    for(int i = 1; i < str.size(); i++) {
        if(SL[i] == 0 && SL[i-1] == 1) {
            SA[--en[str[i]]] = i;
            LMS.push_back(i);
            is_LMS[i] = 1;
        }
    }
    rep(i,var-1) en[i] = st[i+1];
    en[var-1] = str.size();

    rep(i,str.size()) if(SA[i] > 0 && SL[SA[i]-1] == 1) { SA[st[str[SA[i]-1]]++] = SA[i]-1; }
    st[0] = 0;
    for(int i = 1; i < var; i++) st[i] = en[i-1];

    for(int i = 1; i < str.size(); i++) if(SA[i] != -1 && SL[SA[i]] == 0) { SA[i] = -1; }

    for(int i = str.size()-1; i >= 1; i--) if(SA[i] > 0 && SL[SA[i]-1] == 0) { SA[--en[str[SA[i]-1]]] = SA[i]-1; }
    rep(i,var-1) en[i] = st[i+1];
    en[var-1] = str.size();

    int counter = 0;
    vector<int> pre_sa, new_sa;
    rep(i,SA.size()) if(is_LMS[SA[i]] != -1) {
        is_LMS[SA[i]] = ++counter;

        new_sa.clear();
        for(int j = SA[i]; j < SA.size(); j++) {
            new_sa.push_back(str[j]);
            if(j != SA[i] && is_LMS[j] != -1) {
                break;
            }
        }
        if(pre_sa == new_sa) {
            is_LMS[SA[i]] = --counter;
        }
        pre_sa = new_sa;
    }

    vector<int> new_str;
    vector<int> rev((int)LMS.size()+1, 0);
    counter = 0;
    rep(i,is_LMS.size()) {
        if(is_LMS[i] != -1) {
            new_str.push_back(is_LMS[i]);
            rev[counter++] = i;
        }
    }
    vector<int> rec = SA_IS(new_str, new_str.size()+1);

    rep(i,SA.size()) SA[i] = -1;

    for(int i = rec.size()-1; i >= 0; i--) { SA[--en[str[rev[rec[i]]]]] = rev[rec[i]]; }
    rep(i,var-1) en[i] = st[i+1];
    en[var-1] = str.size();

    rep(i,str.size()) if(SA[i] > 0 && SL[SA[i]-1] == 1) { SA[st[str[SA[i]-1]]++] = SA[i]-1; }

    for(int i = 1; i < str.size(); i++) if(SA[i] != -1 && SL[SA[i]] == 0) { SA[i] = -1; }

    for(int i = str.size()-1; i >= 1; i--) if(SA[i] > 0 && SL[SA[i]-1] == 0) { SA[--en[str[SA[i]-1]]] = SA[i]-1; }

    SA.erase(SA.begin());
    return SA;
}

string t;
int q;

bool it_substr(int saidx, const vector<int> &text, const vector<int> &pt) {
  int len = pt.size();
  int n = t.size();
  len = min(len, n - SuffixArray[saidx]);
  int st = SuffixArray[saidx];
  int d = 0;
  rep(i, len) {
    d++;
    if (text[st+i] < pt[i]) return true;
    else if (text[st+i] > pt[i]) return false;
  }
  if (st + d < n) {
    return false;
  }
  else {
    if (d < (int)pt.size()) return true;
    else return false;
  }
}

bool match(const vector<int> &text, const vector<int> &pt) {
    int n = t.size();
    int l = -1, r = n;
    while (r - l > 1) {
        int m = (r + l) / 2;
        if (it_substr(m, text, pt)) l = m;
        else r = m;
    }
    if (r == n) return false;
    //cerr << r << endl;
    int st = SuffixArray[r];
    if (st + (int)pt.size() > n) return false;
    rep(i, pt.size()) {
      if (pt[i] != text[st+i]) return false;
    }
    return true;
}

map<char, int> trans;
int trans_counter = 0;

vector<int> string_to_nums(string& s) {
  rep(i, s.size()) {
    if (trans.find(s[i]) != trans.end()) continue;
    trans[s[i]] = ++trans_counter;
  }
  vector<int> ret;
  rep(i, s.size()) {
    ret.push_back(trans[s[i]]);
  }
  return ret;
}


int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  cin >> t;
  cin >> q;
  vector<int> words = string_to_nums(t);
  SuffixArray = SA_IS(words, 256);
  rep(i, q) {
    string p;
    cin >> p;
    vector<int> pwords = string_to_nums(p);
    if (match(words, pwords)) cout << 1 << endl;
    else cout << 0 << endl;
  }
}


```