#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000001
using namespace std;

int T_length,P_length,range;
int *Rank;
int *Suffix_Array;
int *Work;

char *T,*P;


int strCmp_Suffix_Array(int start){
	int index,ret;

	ret = 0;

	for(index = 0; index < P_length && T[start+index] != '\0'; index++){
		if(P[index] != T[start+index]){
			if(P[index] > T[start+index]){
				ret = 2;
			}else{
				ret = 1;
			}
			break;
		}
	}
	if(ret == 0 && index < P_length){
		ret = 2;
	}
	return ret;
}


bool compare_Suffix_Array(int a,int b){
	if(Rank[a] != Rank[b])return Rank[a] < Rank[b];
	else{
		int rank_a = a + range <= T_length ? Rank[a+range]:-1;
		int rank_b = b + range <= T_length ? Rank[b+range]:-1;
		return rank_a < rank_b;
	}
}

bool isContain(){
	int left = 0,right = T_length,m;
	m = (left+right)/2;

	while(left <= right){
		switch(strCmp_Suffix_Array(Suffix_Array[m])){
		case 0:
			return true;
		case 1:
			right = m-1;
			break;
		case 2:
			left = m+1;
			break;
		}
		m = (left+right)/2;
	}
	return false;
}

void make_Suffix_Array(){
	for(int i = 0; i <= T_length; i++){
		Suffix_Array[i] = i;
		Rank[i] = i < T_length? T[i]:-1;
	}

	for(range = 1; range <= T_length; range*=2){
		sort(Suffix_Array,Suffix_Array+(T_length+1),compare_Suffix_Array);

		Work[Suffix_Array[0]] = 0;
		for(int i = 1; i <= T_length; i++){
			Work[Suffix_Array[i]] = Work[Suffix_Array[i-1]] + (compare_Suffix_Array(Suffix_Array[i-1],Suffix_Array[i])?1:0);
		}
		for(int i = 0; i <= T_length; i++){
			Rank[i] = Work[i];
		}
	}
}


int main(){

	T = new char[1000001];
	scanf("%s",T);

	for(T_length = 0; T[T_length] != '\0'; T_length++);
	Rank = new int[T_length+1];
	Suffix_Array = new int[T_length+1];
	Work = new int[T_length+1];

	make_Suffix_Array();

	int Q;
	scanf("%d",&Q);

	P = new char[1001];
	for(int loop = 0; loop < Q; loop++){
		scanf("%s",P);

		for(P_length = 0; P[P_length] != '\0'; P_length++);

		if(isContain()){
			printf("1\n");
		}else{
			printf("0\n");
		}
	}

	return 0;
}
### Prompt

Please provide a CPP coded solution to the problem described below:

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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000001
using namespace std;

int T_length,P_length,range;
int *Rank;
int *Suffix_Array;
int *Work;

char *T,*P;


int strCmp_Suffix_Array(int start){
	int index,ret;

	ret = 0;

	for(index = 0; index < P_length && T[start+index] != '\0'; index++){
		if(P[index] != T[start+index]){
			if(P[index] > T[start+index]){
				ret = 2;
			}else{
				ret = 1;
			}
			break;
		}
	}
	if(ret == 0 && index < P_length){
		ret = 2;
	}
	return ret;
}


bool compare_Suffix_Array(int a,int b){
	if(Rank[a] != Rank[b])return Rank[a] < Rank[b];
	else{
		int rank_a = a + range <= T_length ? Rank[a+range]:-1;
		int rank_b = b + range <= T_length ? Rank[b+range]:-1;
		return rank_a < rank_b;
	}
}

bool isContain(){
	int left = 0,right = T_length,m;
	m = (left+right)/2;

	while(left <= right){
		switch(strCmp_Suffix_Array(Suffix_Array[m])){
		case 0:
			return true;
		case 1:
			right = m-1;
			break;
		case 2:
			left = m+1;
			break;
		}
		m = (left+right)/2;
	}
	return false;
}

void make_Suffix_Array(){
	for(int i = 0; i <= T_length; i++){
		Suffix_Array[i] = i;
		Rank[i] = i < T_length? T[i]:-1;
	}

	for(range = 1; range <= T_length; range*=2){
		sort(Suffix_Array,Suffix_Array+(T_length+1),compare_Suffix_Array);

		Work[Suffix_Array[0]] = 0;
		for(int i = 1; i <= T_length; i++){
			Work[Suffix_Array[i]] = Work[Suffix_Array[i-1]] + (compare_Suffix_Array(Suffix_Array[i-1],Suffix_Array[i])?1:0);
		}
		for(int i = 0; i <= T_length; i++){
			Rank[i] = Work[i];
		}
	}
}


int main(){

	T = new char[1000001];
	scanf("%s",T);

	for(T_length = 0; T[T_length] != '\0'; T_length++);
	Rank = new int[T_length+1];
	Suffix_Array = new int[T_length+1];
	Work = new int[T_length+1];

	make_Suffix_Array();

	int Q;
	scanf("%d",&Q);

	P = new char[1001];
	for(int loop = 0; loop < Q; loop++){
		scanf("%s",P);

		for(P_length = 0; P[P_length] != '\0'; P_length++);

		if(isContain()){
			printf("1\n");
		}else{
			printf("0\n");
		}
	}

	return 0;
}
```