#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int,int> pp;
typedef pair<pp,int> P;
char t[2500001],p[1001];
int a[2500001],d[1000001],i;
P b[1000001];

void mk(){
  for(i=0;t[i]!=0;i++)
    b[i].f.f=t[i],b[i].s=i;
  b[i].f.f=0,b[i].s=i;

  for(int j=1;j<=i;j*=2){
    sort(b,b+i+1);
    a[b[0].s]=0;
    for(int k=1,l=0;k<=i;k++)
      if(b[k-1].f==b[k].f)a[b[k].s]=l;
      else a[b[k].s]=++l;
    for(int k=0,o=b[0].s;k<=i;k++,o=b[k].s)
      b[k]=P(pp(a[o],a[o+j]),o);
  }
  sort(b,b+i+1);
  a[b[0].s]=0;
  for(int k=1,l=0;k<=i;k++)
    if(b[k-1].f==b[k].f)a[b[k].s]=l;
    else a[b[k].s]=++l;
  for(int j=0;j<=i;j++)d[a[j]]=j;
}

void bs(int n){
  int l=0,r=i,m;
  while(l<r){
    m=(l+r)/2;
    if(strncmp(t+d[m],p,n)<0)l=m+1;
    else r=m;
  }
  if(strncmp(t+d[l],p,n) ==0 )printf("1\n");
  else printf("0\n");
}


int main(){
  int q;
  scanf("%s",t);
  mk();
  cin>>q;
  while(q--&&scanf("%s",p))bs(strlen(p));
  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>
#define f first
#define s second
using namespace std;
typedef pair<int,int> pp;
typedef pair<pp,int> P;
char t[2500001],p[1001];
int a[2500001],d[1000001],i;
P b[1000001];

void mk(){
  for(i=0;t[i]!=0;i++)
    b[i].f.f=t[i],b[i].s=i;
  b[i].f.f=0,b[i].s=i;

  for(int j=1;j<=i;j*=2){
    sort(b,b+i+1);
    a[b[0].s]=0;
    for(int k=1,l=0;k<=i;k++)
      if(b[k-1].f==b[k].f)a[b[k].s]=l;
      else a[b[k].s]=++l;
    for(int k=0,o=b[0].s;k<=i;k++,o=b[k].s)
      b[k]=P(pp(a[o],a[o+j]),o);
  }
  sort(b,b+i+1);
  a[b[0].s]=0;
  for(int k=1,l=0;k<=i;k++)
    if(b[k-1].f==b[k].f)a[b[k].s]=l;
    else a[b[k].s]=++l;
  for(int j=0;j<=i;j++)d[a[j]]=j;
}

void bs(int n){
  int l=0,r=i,m;
  while(l<r){
    m=(l+r)/2;
    if(strncmp(t+d[m],p,n)<0)l=m+1;
    else r=m;
  }
  if(strncmp(t+d[l],p,n) ==0 )printf("1\n");
  else printf("0\n");
}


int main(){
  int q;
  scanf("%s",t);
  mk();
  cin>>q;
  while(q--&&scanf("%s",p))bs(strlen(p));
  return 0;
}
```