#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair< P , int > PP;

int res[1000005];
PP tmp[1000005];
int ans[1000005];

void suffixArray(char* s){
  
  int len=strlen(s);
  
  for(int i=0;i<=len;i++)res[i]=s[i];
  
  for(int k=1;k<=len;k*=2){
    
    for(int i=0;i<=len;i++){
      tmp[i].first.first=res[i];
      tmp[i].first.second=(i+k<=len?res[i+k]:0);
      tmp[i].second=i;
    }
    sort(tmp,tmp+len+1);
    
    int C=0;
    for(int i=0;i<=len;i++){
      int id=tmp[i].second;
      if(i&& (tmp[i-1].first<tmp[i].first))C++;
      res[id]=C;
    }
  }

  for(int i=0;i<=len;i++)ans[ res[i] ]=i;
}

char s[1000005];
char t[1000005];
int main(){
  scanf("%s",s);
  int lenS=strlen(s);
  
  suffixArray(s);

  int Q;
  scanf("%d",&Q);
  
  while(Q--){
    scanf("%s",t);
    int len=strlen(t);
    int l=0,r=lenS+1,m;
    while(r-l>1){
      m=(l+r)/2;
      if( strncmp( s+ans[m] , t ,len ) <=0 )l=m;
      else r=m;
    }
    if(strncmp(s+ans[l],t,len)==0)printf("1\n");
    else printf("0\n");
  }
  
  /*
  for(int i=0;i<(int)ans.size();i++){
    printf("%d %s\n",ans[i], (s+ans[i]) );
  }
  */
  
  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<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair< P , int > PP;

int res[1000005];
PP tmp[1000005];
int ans[1000005];

void suffixArray(char* s){
  
  int len=strlen(s);
  
  for(int i=0;i<=len;i++)res[i]=s[i];
  
  for(int k=1;k<=len;k*=2){
    
    for(int i=0;i<=len;i++){
      tmp[i].first.first=res[i];
      tmp[i].first.second=(i+k<=len?res[i+k]:0);
      tmp[i].second=i;
    }
    sort(tmp,tmp+len+1);
    
    int C=0;
    for(int i=0;i<=len;i++){
      int id=tmp[i].second;
      if(i&& (tmp[i-1].first<tmp[i].first))C++;
      res[id]=C;
    }
  }

  for(int i=0;i<=len;i++)ans[ res[i] ]=i;
}

char s[1000005];
char t[1000005];
int main(){
  scanf("%s",s);
  int lenS=strlen(s);
  
  suffixArray(s);

  int Q;
  scanf("%d",&Q);
  
  while(Q--){
    scanf("%s",t);
    int len=strlen(t);
    int l=0,r=lenS+1,m;
    while(r-l>1){
      m=(l+r)/2;
      if( strncmp( s+ans[m] , t ,len ) <=0 )l=m;
      else r=m;
    }
    if(strncmp(s+ans[l],t,len)==0)printf("1\n");
    else printf("0\n");
  }
  
  /*
  for(int i=0;i<(int)ans.size();i++){
    printf("%d %s\n",ans[i], (s+ans[i]) );
  }
  */
  
  return 0;
}
```