#include <bits/stdc++.h>
#define N 1<<20
using namespace std;

struct P{
  int a,b,idx;
  P(){a=b=idx=0;}
  P(int a,int b,int idx):a(a),b(b),idx(idx){};
  bool operator < (const P &A) const{
    if(a!=A.a) return a>A.a;
    return b>A.b;
  }
};

char ch[N];
P r[N];
int n;

vector<int> Sort(){
    vector <int> R(n+1),res(n+1);
  
  for(int i=0;i<=n;i++) R[i]=ch[i];
  
  for(int i=1;i<=n;i*=2){
    for(int j=0;j<=n;j++)r[j]=P(R[j],(j+i<=n)? R[j+i]:0,j);
    sort(r,r+n+1);
    R[r[0].idx]=n;
    for(int j=1,C=n;j<=n;j++){
      if(r[j-1]<r[j]) C--;
      R[r[j].idx]=C;
    }

    //    for(int j=0;j<=n;j++)cout<<R[j]<<' ';
    //			   cout<<endl;

  }
  for(int i=0;i<=n;i++) res[R[i]]=i;
  return res;
}

int check(vector <int> &a,char *x){
  /*
  cout<<'!'<<endl;
  for(int i=0;i<n+1;i++){
    printf("%d %s\n",a[i],ch+a[i]);
  }
  cout<<'!'<<endl;
  */
  int L=0,M,R=n;
  int m=strlen(x);

  while(L<R){
    M=(L+R)/2;
    if(strncmp(ch+a[M],x,m)<0)L=M+1;
    else R=M;
  }

  return strncmp(ch+a[L],x,m)==0;
}

int main(){
  scanf("%s",ch);
  n=strlen(ch);
  int q;
  cin>>q;
  vector <int> Rank=Sort();
  char a[1001];

  while(q--){
    scanf("%s",a);
    printf("%d\n",check(Rank,a));
  }
  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 <bits/stdc++.h>
#define N 1<<20
using namespace std;

struct P{
  int a,b,idx;
  P(){a=b=idx=0;}
  P(int a,int b,int idx):a(a),b(b),idx(idx){};
  bool operator < (const P &A) const{
    if(a!=A.a) return a>A.a;
    return b>A.b;
  }
};

char ch[N];
P r[N];
int n;

vector<int> Sort(){
    vector <int> R(n+1),res(n+1);
  
  for(int i=0;i<=n;i++) R[i]=ch[i];
  
  for(int i=1;i<=n;i*=2){
    for(int j=0;j<=n;j++)r[j]=P(R[j],(j+i<=n)? R[j+i]:0,j);
    sort(r,r+n+1);
    R[r[0].idx]=n;
    for(int j=1,C=n;j<=n;j++){
      if(r[j-1]<r[j]) C--;
      R[r[j].idx]=C;
    }

    //    for(int j=0;j<=n;j++)cout<<R[j]<<' ';
    //			   cout<<endl;

  }
  for(int i=0;i<=n;i++) res[R[i]]=i;
  return res;
}

int check(vector <int> &a,char *x){
  /*
  cout<<'!'<<endl;
  for(int i=0;i<n+1;i++){
    printf("%d %s\n",a[i],ch+a[i]);
  }
  cout<<'!'<<endl;
  */
  int L=0,M,R=n;
  int m=strlen(x);

  while(L<R){
    M=(L+R)/2;
    if(strncmp(ch+a[M],x,m)<0)L=M+1;
    else R=M;
  }

  return strncmp(ch+a[L],x,m)==0;
}

int main(){
  scanf("%s",ch);
  n=strlen(ch);
  int q;
  cin>>q;
  vector <int> Rank=Sort();
  char a[1001];

  while(q--){
    scanf("%s",a);
    printf("%d\n",check(Rank,a));
  }
  return 0;
}
```