#include<bits/stdc++.h>

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

typedef long long ll;
typedef pair<int, int> P;

#define MAX 100005
#define INF 1001001001

int main(int, char**)
{
  string t;
  cin >> t;

  int ts = t.size();
  vector<int> sa(ts+1), rank(ts+1);
  int k;

  auto comp_sa = [&] (int i, int j) -> bool {
    if (rank[i] != rank[j]) return rank[i] < rank[j];
    int ri = i+k<=ts ? rank[i+k] : -1;
    int rj = j+k<=ts ? rank[j+k] : -1;
    return ri < rj;
  };

  rep(i,ts+1) {
    sa[i] = i;
    rank[i] = i < ts ? t[i] : -1;
  }
  for (k = 1; k <= ts; k <<= 1) {
    sort(sa.begin(), sa.end(), comp_sa);
    int tmpr = 0;
    vector<int> tmpr_v(ts+1);
    rep(i,ts+1) {
      tmpr_v[sa[i]] = tmpr;
      if (i < ts && comp_sa(sa[i], sa[i+1])) tmpr++;
    }
    rep(i,ts+1) rank[i] = tmpr_v[i];
  }

  int q;
  cin >> q;
  vector<int> ans;
  rep(i,q) {
    string p;
    cin >> p;

    int l = 0, r = ts;
    int found = 0;
    while (r>=l) {
      int m = (r+l)/2;
      int res = t.compare(sa[m], p.size(), p);
      if (res < 0) l = m+1;
      else if (res > 0) r = m-1;
      else {
        found = 1;
        break;
      }
    }
    ans.push_back(found);
  }
  for (auto a : ans) cout << a << endl;

  return 0;
}


### Prompt

Please create a solution in Cpp 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<(n);i++)

typedef long long ll;
typedef pair<int, int> P;

#define MAX 100005
#define INF 1001001001

int main(int, char**)
{
  string t;
  cin >> t;

  int ts = t.size();
  vector<int> sa(ts+1), rank(ts+1);
  int k;

  auto comp_sa = [&] (int i, int j) -> bool {
    if (rank[i] != rank[j]) return rank[i] < rank[j];
    int ri = i+k<=ts ? rank[i+k] : -1;
    int rj = j+k<=ts ? rank[j+k] : -1;
    return ri < rj;
  };

  rep(i,ts+1) {
    sa[i] = i;
    rank[i] = i < ts ? t[i] : -1;
  }
  for (k = 1; k <= ts; k <<= 1) {
    sort(sa.begin(), sa.end(), comp_sa);
    int tmpr = 0;
    vector<int> tmpr_v(ts+1);
    rep(i,ts+1) {
      tmpr_v[sa[i]] = tmpr;
      if (i < ts && comp_sa(sa[i], sa[i+1])) tmpr++;
    }
    rep(i,ts+1) rank[i] = tmpr_v[i];
  }

  int q;
  cin >> q;
  vector<int> ans;
  rep(i,q) {
    string p;
    cin >> p;

    int l = 0, r = ts;
    int found = 0;
    while (r>=l) {
      int m = (r+l)/2;
      int res = t.compare(sa[m], p.size(), p);
      if (res < 0) l = m+1;
      else if (res > 0) r = m-1;
      else {
        found = 1;
        break;
      }
    }
    ans.push_back(found);
  }
  for (auto a : ans) cout << a << endl;

  return 0;
}


```