#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }


struct SuffixArray {
	int n, k;
	string s;
	vector<int> ord, tmp, left;
	SuffixArray(const string &s) :s(s), n(s.size()), ord(n + 1), tmp(n + 1), left(n + 1) {
		for (int i = 0; i <= n; i++) {
			left[i] = i;
			ord[i] = i < n ? s[i] : -1;
		}
		auto compare = [&](int i, int j) {
			if (ord[i] != ord[j])return ord[i] < ord[j];
			else {
				int ri = i + k <= n ? ord[i + k] : -1;
				int rj = j + k <= n ? ord[j + k] : -1;
				return ri < rj;
			}
		};
		for (k = 1; k <= n; k *= 2) {
			sort(left.begin(), left.end(), compare);
			tmp[left[0]] = 0;
			for (int i = 1; i <= n; i++) {
				tmp[left[i]] = tmp[left[i - 1]] + (compare(left[i - 1], left[i]) ? 1 : 0);
			}
			ord = tmp;
		}
		dump(ord, tmp, left);
	}
	int search(const string &pattern) {
		int m = pattern.size();
		auto f = [&](int x) {
			string t = s.substr(left[x], min(m, n - left[x]));
			dump(x, t);
			return pattern <= t;
		};
		auto binarySearch = [&](int ng, int ok) {
			if (f(ng))return ng;
			while (ng + 1 < ok) {
				int m = (ng + ok) / 2;
				if (f(m))
					ok = m;
				else
					ng = m;
			}
			return ok;
		};
		int ok = binarySearch(0, n + 1);
		if (ok > n)
			return -1;
		else {
			string t = s.substr(left[ok], min(m, n - left[ok]));
			return pattern == t ? left[ok] : -1;
		}
	}
};

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string T; cin >> T;
	int Q; cin >> Q;
	SuffixArray sa(T);
	rep(i, 0, Q) {
		string P; cin >> P;
		cout << (sa.search(P) != -1) << endl;
	}
	return 0;
}
### Prompt

Generate 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"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }


struct SuffixArray {
	int n, k;
	string s;
	vector<int> ord, tmp, left;
	SuffixArray(const string &s) :s(s), n(s.size()), ord(n + 1), tmp(n + 1), left(n + 1) {
		for (int i = 0; i <= n; i++) {
			left[i] = i;
			ord[i] = i < n ? s[i] : -1;
		}
		auto compare = [&](int i, int j) {
			if (ord[i] != ord[j])return ord[i] < ord[j];
			else {
				int ri = i + k <= n ? ord[i + k] : -1;
				int rj = j + k <= n ? ord[j + k] : -1;
				return ri < rj;
			}
		};
		for (k = 1; k <= n; k *= 2) {
			sort(left.begin(), left.end(), compare);
			tmp[left[0]] = 0;
			for (int i = 1; i <= n; i++) {
				tmp[left[i]] = tmp[left[i - 1]] + (compare(left[i - 1], left[i]) ? 1 : 0);
			}
			ord = tmp;
		}
		dump(ord, tmp, left);
	}
	int search(const string &pattern) {
		int m = pattern.size();
		auto f = [&](int x) {
			string t = s.substr(left[x], min(m, n - left[x]));
			dump(x, t);
			return pattern <= t;
		};
		auto binarySearch = [&](int ng, int ok) {
			if (f(ng))return ng;
			while (ng + 1 < ok) {
				int m = (ng + ok) / 2;
				if (f(m))
					ok = m;
				else
					ng = m;
			}
			return ok;
		};
		int ok = binarySearch(0, n + 1);
		if (ok > n)
			return -1;
		else {
			string t = s.substr(left[ok], min(m, n - left[ok]));
			return pattern == t ? left[ok] : -1;
		}
	}
};

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string T; cin >> T;
	int Q; cin >> Q;
	SuffixArray sa(T);
	rep(i, 0, Q) {
		string P; cin >> P;
		cout << (sa.search(P) != -1) << endl;
	}
	return 0;
}
```