#include <bits/stdc++.h>
#define MAX_N 1000000
typedef unsigned long long ull;
using namespace std;

int n, k;
int Rank[MAX_N + 1];
int tmp[MAX_N + 1];

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

void Construct_SA(const string &S, vector<int> &SA) {
	n = S.length();
	SA = vector<int>(n + 1);

	for (int i = 0; i <= n;i++) {
		SA[i] = i;
		Rank[i] = i < n ? S[i] : -1;
	}

	for (k = 1; k <= n; k *= 2) {
		sort(SA.begin(), SA.end(), Compare_SA);

		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++) {
			Rank[i] = tmp[i];
		}
	}
}

bool Contain(const string &S, const vector<int> &SA, const string &T) {
	int a = 0, b = S.length();
	while (b - a > 1) {
		int c = (a + b) / 2;
		if (S.compare(SA[c], T.length(), T) < 0) a = c;
		else b = c;
	}
	return S.compare(SA[b], T.length(), T) == 0;
}

int main()
{
	int Q;
	string T, P;
	vector<int> SA;
	cin.sync_with_stdio(false);
	cin >> T;
	Construct_SA(T, SA);
	cin >> Q;
	while (Q--) {
		cin >> P;
		cout << Contain(T, SA, P) << endl;
	}
	return 0;
}
### 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 <bits/stdc++.h>
#define MAX_N 1000000
typedef unsigned long long ull;
using namespace std;

int n, k;
int Rank[MAX_N + 1];
int tmp[MAX_N + 1];

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

void Construct_SA(const string &S, vector<int> &SA) {
	n = S.length();
	SA = vector<int>(n + 1);

	for (int i = 0; i <= n;i++) {
		SA[i] = i;
		Rank[i] = i < n ? S[i] : -1;
	}

	for (k = 1; k <= n; k *= 2) {
		sort(SA.begin(), SA.end(), Compare_SA);

		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++) {
			Rank[i] = tmp[i];
		}
	}
}

bool Contain(const string &S, const vector<int> &SA, const string &T) {
	int a = 0, b = S.length();
	while (b - a > 1) {
		int c = (a + b) / 2;
		if (S.compare(SA[c], T.length(), T) < 0) a = c;
		else b = c;
	}
	return S.compare(SA[b], T.length(), T) == 0;
}

int main()
{
	int Q;
	string T, P;
	vector<int> SA;
	cin.sync_with_stdio(false);
	cin >> T;
	Construct_SA(T, SA);
	cin >> Q;
	while (Q--) {
		cin >> P;
		cout << Contain(T, SA, P) << endl;
	}
	return 0;
}
```