#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>

#define MAX 1000000

using namespace std;

int n,k;
int rankk[MAX+1];
int tmp[MAX+1];
int sa[MAX+1];

bool compare_sa(int i,int j){
	if(rankk[i]!=rankk[j]) return rankk[i]<rankk[j];
	else{
		int ri=(i+k<=n ? rankk[i+k]:-1);
		int rj=(j+k<=n ? rankk[j+k]:-1);
		return ri<rj;
	}
}

void construct_sa(string S){
	n = S.length();
	//???????¨???????, 1????????§, rank????????????????????§??????.
	for(int i=0;i<=n;i++){
		sa[i]=i;
		rankk[i]=(i<n ? S[i]:-1);
	}
	
	//k??????????????????sort?????????????????¨?????????, 2k????????§sort
	for(k=1;k<=n;k*=2){
		sort(sa,sa+n+1,compare_sa);
		//tmp????¬????rank????¨????, rank????§?????????????.
		tmp[sa[0]]=0;
		for(int i=1;i<=n;i++){
			tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i]) ? 1:0);
		}
		for(int i=0;i<=n;i++){
			rankk[i]=tmp[i];
		}
	}
}

bool contains(string S, string P){
	int a=0;
	int b=S.length();
	while(b-a>1){
		int c=(a+b)/2;
		//S???sa[C]???????????????|T|????????¨T?????????
		if(S.compare(sa[c],P.length(),P)<0) a=c;
		else b=c;
	}
	return S.compare(sa[b],P.length(),P)==0;
}

int main(){
	int q;
	bool ans;
	string T,P;
	cin >> T;
	construct_sa(T);//Construct Suffix Array
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		cin.ignore();
		cin >> P;
		ans = contains(T,P);
		if(ans==true)
		printf("1\n");
		else
		printf("0\n");
	}
}
### 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<cstdio>
#include<algorithm>
#include<string>

#define MAX 1000000

using namespace std;

int n,k;
int rankk[MAX+1];
int tmp[MAX+1];
int sa[MAX+1];

bool compare_sa(int i,int j){
	if(rankk[i]!=rankk[j]) return rankk[i]<rankk[j];
	else{
		int ri=(i+k<=n ? rankk[i+k]:-1);
		int rj=(j+k<=n ? rankk[j+k]:-1);
		return ri<rj;
	}
}

void construct_sa(string S){
	n = S.length();
	//???????¨???????, 1????????§, rank????????????????????§??????.
	for(int i=0;i<=n;i++){
		sa[i]=i;
		rankk[i]=(i<n ? S[i]:-1);
	}
	
	//k??????????????????sort?????????????????¨?????????, 2k????????§sort
	for(k=1;k<=n;k*=2){
		sort(sa,sa+n+1,compare_sa);
		//tmp????¬????rank????¨????, rank????§?????????????.
		tmp[sa[0]]=0;
		for(int i=1;i<=n;i++){
			tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i]) ? 1:0);
		}
		for(int i=0;i<=n;i++){
			rankk[i]=tmp[i];
		}
	}
}

bool contains(string S, string P){
	int a=0;
	int b=S.length();
	while(b-a>1){
		int c=(a+b)/2;
		//S???sa[C]???????????????|T|????????¨T?????????
		if(S.compare(sa[c],P.length(),P)<0) a=c;
		else b=c;
	}
	return S.compare(sa[b],P.length(),P)==0;
}

int main(){
	int q;
	bool ans;
	string T,P;
	cin >> T;
	construct_sa(T);//Construct Suffix Array
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		cin.ignore();
		cin >> P;
		ans = contains(T,P);
		if(ans==true)
		printf("1\n");
		else
		printf("0\n");
	}
}
```