#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define dbg(x) cout<<#x"="<<x<<endl

vector<int> construct_sa(const string& S){
  vector<int> SA, ranks, tmp;
  int N = S.length();

  SA.resize(N + 1);
  ranks.resize(N + 1);
  tmp.resize(N + 1);

  for(int i = 0; i <= N; i++){
    SA[i] = i;
    ranks[i] = (i < N ? S[i] : -1);
  }

  for(int k = 1; k <= N; k *= 2){
    auto f = [&](const int& a,const int& b){
      if(ranks[a] != ranks[b]) return ranks[a] < ranks[b];
      else{
        int ra = (a + k <= N ? ranks[a + k] : -1);
        int rb = (b + k <= N ? ranks[b + k] : -1);
        return ra < rb;
      }
    };

    sort(SA.begin(), SA.end(), f);

    tmp[SA[0]] = 0;
    for(int i = 1; i <= N; i++){
      tmp[SA[i]] = tmp[SA[i-1]] + (f(SA[i-1], SA[i]) ? 1 : 0);
    }
    for(int i = 0; i <= N; i++){
      ranks[i] = tmp[i];
    }
  }
  return SA;
}

//int main(int argc, char **argv){
int main(){
  /*if(argc < 3){
    cerr << "Few arguments." << endl;
    return 0;
  }*/


  string S;
  cin>>S;
  int N=S.size();
  vector<int> SA=construct_sa(S);

  int Q;
  cin>>Q;
  while(Q--){
    string T;
    cin>>T;
    int L=T.size();
    int l=0,r=N+1;
    rep(i,L){
      int nl,nr;

      {
        int lb=l-1,ub=r;
        while(ub-lb>1){
          int mid=(lb+ub)/2;
          if(SA[mid]+i<N&&S[SA[mid]+i]>=T[i]) ub=mid;
          else lb=mid;
        }
        nl=ub;
      }
      {
        int lb=l-1,ub=r;
        while(ub-lb>1){
          int mid=(lb+ub)/2;
          if(SA[mid]+i<N&&S[SA[mid]+i]>T[i]) ub=mid;
          else lb=mid;
        }
        nr=ub;
      }

      l=nl; r=nr;
    }

    if(l!=r)printf("1\n");
    else printf("0\n");
  }

  return 0;
}


### Prompt

Please formulate 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 <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define dbg(x) cout<<#x"="<<x<<endl

vector<int> construct_sa(const string& S){
  vector<int> SA, ranks, tmp;
  int N = S.length();

  SA.resize(N + 1);
  ranks.resize(N + 1);
  tmp.resize(N + 1);

  for(int i = 0; i <= N; i++){
    SA[i] = i;
    ranks[i] = (i < N ? S[i] : -1);
  }

  for(int k = 1; k <= N; k *= 2){
    auto f = [&](const int& a,const int& b){
      if(ranks[a] != ranks[b]) return ranks[a] < ranks[b];
      else{
        int ra = (a + k <= N ? ranks[a + k] : -1);
        int rb = (b + k <= N ? ranks[b + k] : -1);
        return ra < rb;
      }
    };

    sort(SA.begin(), SA.end(), f);

    tmp[SA[0]] = 0;
    for(int i = 1; i <= N; i++){
      tmp[SA[i]] = tmp[SA[i-1]] + (f(SA[i-1], SA[i]) ? 1 : 0);
    }
    for(int i = 0; i <= N; i++){
      ranks[i] = tmp[i];
    }
  }
  return SA;
}

//int main(int argc, char **argv){
int main(){
  /*if(argc < 3){
    cerr << "Few arguments." << endl;
    return 0;
  }*/


  string S;
  cin>>S;
  int N=S.size();
  vector<int> SA=construct_sa(S);

  int Q;
  cin>>Q;
  while(Q--){
    string T;
    cin>>T;
    int L=T.size();
    int l=0,r=N+1;
    rep(i,L){
      int nl,nr;

      {
        int lb=l-1,ub=r;
        while(ub-lb>1){
          int mid=(lb+ub)/2;
          if(SA[mid]+i<N&&S[SA[mid]+i]>=T[i]) ub=mid;
          else lb=mid;
        }
        nl=ub;
      }
      {
        int lb=l-1,ub=r;
        while(ub-lb>1){
          int mid=(lb+ub)/2;
          if(SA[mid]+i<N&&S[SA[mid]+i]>T[i]) ub=mid;
          else lb=mid;
        }
        nr=ub;
      }

      l=nl; r=nr;
    }

    if(l!=r)printf("1\n");
    else printf("0\n");
  }

  return 0;
}


```