#include<bits/stdc++.h>
using namespace std;
int ranker_MAX[1000005];
int tenpaman[1000005];
int kc,len;
bool compare_sa(int i,int j){
  return
    ranker_MAX[i]!=ranker_MAX[j]?
    ranker_MAX[i]<ranker_MAX[j]:
    (i+kc<=len?ranker_MAX[i+kc]:-1)<(j+kc<=len?ranker_MAX[j+kc]:-1);
}

void construct_sa(char* S,int *sachiko){
  len=strlen(S);
  for(int i=0;i<=len;i++){
    sachiko[i]=i;
    ranker_MAX[i]=i<len?S[i]:-1;
  }
  for(kc=1;kc<=len;kc*=2){
    sort(sachiko,sachiko+len+1,compare_sa);
    tenpaman[sachiko[0]]=0;
    for(int i=1;i<=len;i++){
      tenpaman[sachiko[i]]=tenpaman[sachiko[i-1]]+compare_sa(sachiko[i-1],sachiko[i]);
    }
    for(int i=0;i<=len;i++)ranker_MAX[i]=tenpaman[i];
  }
}
int n,m;
char strttenannkaiiiyone[1000005];
char t[1000005];
int sachiko[1000005];

int main(){
  scanf("%s",strttenannkaiiiyone);
  n=strlen(strttenannkaiiiyone);
  construct_sa(strttenannkaiiiyone,sachiko);
  scanf("%d",&m);
  while(m--){
    scanf("%s",t);
    int k=strlen(t);
    int l=0,r=n+1,m;
    while(l+1<r){
      m=(l+r)/2;
      if(strncmp(strttenannkaiiiyone+sachiko[m],t,k)<=0)l=m;
      else r=m;
    }
    printf("%d\n",(strncmp(strttenannkaiiiyone+sachiko[l],t,k)==0));
  }
  return 0;
}


### Prompt

Create a solution in cpp for 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;
int ranker_MAX[1000005];
int tenpaman[1000005];
int kc,len;
bool compare_sa(int i,int j){
  return
    ranker_MAX[i]!=ranker_MAX[j]?
    ranker_MAX[i]<ranker_MAX[j]:
    (i+kc<=len?ranker_MAX[i+kc]:-1)<(j+kc<=len?ranker_MAX[j+kc]:-1);
}

void construct_sa(char* S,int *sachiko){
  len=strlen(S);
  for(int i=0;i<=len;i++){
    sachiko[i]=i;
    ranker_MAX[i]=i<len?S[i]:-1;
  }
  for(kc=1;kc<=len;kc*=2){
    sort(sachiko,sachiko+len+1,compare_sa);
    tenpaman[sachiko[0]]=0;
    for(int i=1;i<=len;i++){
      tenpaman[sachiko[i]]=tenpaman[sachiko[i-1]]+compare_sa(sachiko[i-1],sachiko[i]);
    }
    for(int i=0;i<=len;i++)ranker_MAX[i]=tenpaman[i];
  }
}
int n,m;
char strttenannkaiiiyone[1000005];
char t[1000005];
int sachiko[1000005];

int main(){
  scanf("%s",strttenannkaiiiyone);
  n=strlen(strttenannkaiiiyone);
  construct_sa(strttenannkaiiiyone,sachiko);
  scanf("%d",&m);
  while(m--){
    scanf("%s",t);
    int k=strlen(t);
    int l=0,r=n+1,m;
    while(l+1<r){
      m=(l+r)/2;
      if(strncmp(strttenannkaiiiyone+sachiko[m],t,k)<=0)l=m;
      else r=m;
    }
    printf("%d\n",(strncmp(strttenannkaiiiyone+sachiko[l],t,k)==0));
  }
  return 0;
}


```