#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
using namespace std;
#define MAX_N 1100000
int Rank[MAX_N], x[MAX_N];
int SA[MAX_N]; string S, T; int V;
bool Compare(int p, int q) {
	if (Rank[p] < Rank[q])return true;
	if (Rank[p] > Rank[q])return false;
	int D1 = -1, D2 = -1;
	if (p + V <= S.size())D1 = Rank[p + V];
	if (q + V <= S.size())D2 = Rank[q + V];
	if (D1 < D2)return true;
	return false;
}
void Build() {
	for (int i = 0; i < S.size(); i++) { SA[i] = i; Rank[i] = S[i]; }
	SA[S.size()] = S.size(); Rank[S.size()] = -1;
	for (V = 1; V <= S.size(); V *= 2) {
		sort(SA, SA + S.size() + 1, Compare);
		x[SA[0]] = 0;
		for (int i = 1; i <= S.size(); i++) {
			x[SA[i]] = x[SA[i - 1]] + Compare(SA[i - 1], SA[i]);
		}
		for (int i = 0; i <= S.size(); i++)Rank[i] = x[i];
	}
}
int hantei(int C, string &V2) {
	int H = min(S.size() - C, V2.size());
	for (int i = 0; i < H; i++) {
		if (S[i + C] < V2[i])return -1;
		if (S[i + C] > V2[i])return 1;
	}
	return 0;
}
int main() {
	cin >> S; S += '!'; int Q; cin >> Q; Build();
	for (int i = 0; i < Q; i++) {
		cin >> T; int L = 0, R = S.size() + 1, M;
		while (L + 1 < R) {
			M = (L + R) / 2;
			if (hantei(SA[M], T) <= 0)L = M;
			else { R = M; }
		}
		if (hantei(SA[L], T) == 0)cout << "1" << endl;
		else cout << "0" << endl;
	}
	return 0;
}
### Prompt

Please create a solution in cpp 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<string>
#include<algorithm>
#include<functional>
using namespace std;
#define MAX_N 1100000
int Rank[MAX_N], x[MAX_N];
int SA[MAX_N]; string S, T; int V;
bool Compare(int p, int q) {
	if (Rank[p] < Rank[q])return true;
	if (Rank[p] > Rank[q])return false;
	int D1 = -1, D2 = -1;
	if (p + V <= S.size())D1 = Rank[p + V];
	if (q + V <= S.size())D2 = Rank[q + V];
	if (D1 < D2)return true;
	return false;
}
void Build() {
	for (int i = 0; i < S.size(); i++) { SA[i] = i; Rank[i] = S[i]; }
	SA[S.size()] = S.size(); Rank[S.size()] = -1;
	for (V = 1; V <= S.size(); V *= 2) {
		sort(SA, SA + S.size() + 1, Compare);
		x[SA[0]] = 0;
		for (int i = 1; i <= S.size(); i++) {
			x[SA[i]] = x[SA[i - 1]] + Compare(SA[i - 1], SA[i]);
		}
		for (int i = 0; i <= S.size(); i++)Rank[i] = x[i];
	}
}
int hantei(int C, string &V2) {
	int H = min(S.size() - C, V2.size());
	for (int i = 0; i < H; i++) {
		if (S[i + C] < V2[i])return -1;
		if (S[i + C] > V2[i])return 1;
	}
	return 0;
}
int main() {
	cin >> S; S += '!'; int Q; cin >> Q; Build();
	for (int i = 0; i < Q; i++) {
		cin >> T; int L = 0, R = S.size() + 1, M;
		while (L + 1 < R) {
			M = (L + R) / 2;
			if (hantei(SA[M], T) <= 0)L = M;
			else { R = M; }
		}
		if (hantei(SA[L], T) == 0)cout << "1" << endl;
		else cout << "0" << endl;
	}
	return 0;
}
```