#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)



//segmenttree(min)
struct Segmenttree {
	static const int N = 1 << 20;
	vector<ll>seg;
	vector<ll>idx;
	void st(ll p, ll v) {
		p += N - 1;
		seg[p] = v;
		idx[p] = p - N + 1;
		while (p > 0) {
			p = (p - 1) / 2;
			seg[p] = min(seg[2 * p + 1], seg[2 * p + 2]);
			if (seg[2 * p + 1] > seg[2 * p + 2])idx[p] = idx[2 * p + 2];
			else if (seg[2 * p + 1] < seg[2 * p + 2])idx[p] = idx[2 * p + 1];
			else idx[p] = min(idx[2 * p + 1], idx[2 * p + 2]);
		}
	}
	pair<ll, ll> query(ll l, ll r, ll a, ll b, ll k) {
		if (r <= a || b <= l)return { inf,inf };
		if (l <= a && b <= r)return { seg[k],idx[k] };
		ll m = (a + b) / 2;
		auto p1 = query(l, r, a, m, 2 * k + 1);
		auto p2 = query(l, r, m, b, 2 * k + 2);
		if (p1.first < p2.first) return p1;
		else if (p1.first > p2.first)return p2;
		else return { p1.first,min(p1.second,p2.second) };
	}

	void init() {
		seg.resize(2 * N);
		idx.resize(2 * N);
		for (int i = 0; i < 2 * N; i++)seg[i] = inf;
	}
	//[l,r]
	ll get(int l, int r) {
		return query(l, r + 1, 0, N, 0).first;
	}
	ll getidx(int l, int r) {
		return query(l, r + 1, 0, N, 0).second;
	}
	pair<ll, ll>getp(int l, int r) {
		return query(l, r + 1, 0, N, 0);
	}
};

//suffix array
struct suffixarray {
	vector<int>rk, rklcp, tmp, sa, lcp;
	int n, k;
	string str;		
	Segmenttree seg = Segmenttree();

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


	void construct_sa(string S) {
		str = S;
		n = str.size();
		rk.resize(n + 1);
		rklcp.resize(n + 1);
		tmp.resize(n + 1);
		sa.resize(n + 1);
		lcp.resize(n + 1);

		for (int i = 0; i <= n; i++) {
			sa[i] = i;
			rk[i] = i < n ? str[i] : -1;
		}
		for (k = 1; k <= n; k *= 2) {
			sort(all(sa), [&](int i, int j) {
				if (rk[i] != rk[j])return rk[i] < rk[j];
				else {
					int ri = i + k <= n ? rk[i + k] : -1;
					int rj = j + k <= n ? rk[j + k] : -1;
					return ri < rj;
				}
			});
			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++)rk[i] = tmp[i];
		}
		construct_lcp();
	}


	void construct_lcp() {
		for (int i = 0; i <= n; i++)rklcp[sa[i]] = i;
		int h = 0;
		lcp[0] = 0;
		for (int i = 0; i < n; i++) {
			int j = sa[rklcp[i] - 1];
			if (h > 0)h--;
			while (j + h < n && i + h < n) {
				if (str[j + h] != str[i + h])break;
				h++;
			}
			lcp[rklcp[i] - 1] = h;
		}
		seg.init();
		for (int i = 0; i < n; i++)seg.st(i, lcp[i]);
	}

	pair<int, int> get_lcp(string T, int si, int offset) {
		int i = offset;
		si += offset;
		while (i < T.size() && si < n) {
			if (T[i] != str[si]) {
				return { i,T[i] - str[si] };
			}
			i++;
			si++;
		}
		return { i,0 };
	}

	int search(string T) {
		int ok = 0, ng = n + 1;
		int Llcp = 0;
		while (ng - ok > 1) {
			int mid = (ok + ng) / 2;
			int nlcp = seg.get(ok,mid-1);
			if (Llcp < nlcp)ok = mid;
			else if (Llcp > nlcp)ng = mid;
			else {
				auto p = get_lcp(T, sa[mid], Llcp);
				if (p.second >= 0) {
					ok = mid;
					Llcp = p.first;
				}
				else ng = mid;
			}
		}
		return get_lcp(T,sa[ok],Llcp).first == T.size();
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	string T;
	cin >> T;

	suffixarray sa;
	sa.construct_sa(T);

	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		string P;
		cin >> P;
		puts(sa.search(P));
	}

	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<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)



//segmenttree(min)
struct Segmenttree {
	static const int N = 1 << 20;
	vector<ll>seg;
	vector<ll>idx;
	void st(ll p, ll v) {
		p += N - 1;
		seg[p] = v;
		idx[p] = p - N + 1;
		while (p > 0) {
			p = (p - 1) / 2;
			seg[p] = min(seg[2 * p + 1], seg[2 * p + 2]);
			if (seg[2 * p + 1] > seg[2 * p + 2])idx[p] = idx[2 * p + 2];
			else if (seg[2 * p + 1] < seg[2 * p + 2])idx[p] = idx[2 * p + 1];
			else idx[p] = min(idx[2 * p + 1], idx[2 * p + 2]);
		}
	}
	pair<ll, ll> query(ll l, ll r, ll a, ll b, ll k) {
		if (r <= a || b <= l)return { inf,inf };
		if (l <= a && b <= r)return { seg[k],idx[k] };
		ll m = (a + b) / 2;
		auto p1 = query(l, r, a, m, 2 * k + 1);
		auto p2 = query(l, r, m, b, 2 * k + 2);
		if (p1.first < p2.first) return p1;
		else if (p1.first > p2.first)return p2;
		else return { p1.first,min(p1.second,p2.second) };
	}

	void init() {
		seg.resize(2 * N);
		idx.resize(2 * N);
		for (int i = 0; i < 2 * N; i++)seg[i] = inf;
	}
	//[l,r]
	ll get(int l, int r) {
		return query(l, r + 1, 0, N, 0).first;
	}
	ll getidx(int l, int r) {
		return query(l, r + 1, 0, N, 0).second;
	}
	pair<ll, ll>getp(int l, int r) {
		return query(l, r + 1, 0, N, 0);
	}
};

//suffix array
struct suffixarray {
	vector<int>rk, rklcp, tmp, sa, lcp;
	int n, k;
	string str;		
	Segmenttree seg = Segmenttree();

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


	void construct_sa(string S) {
		str = S;
		n = str.size();
		rk.resize(n + 1);
		rklcp.resize(n + 1);
		tmp.resize(n + 1);
		sa.resize(n + 1);
		lcp.resize(n + 1);

		for (int i = 0; i <= n; i++) {
			sa[i] = i;
			rk[i] = i < n ? str[i] : -1;
		}
		for (k = 1; k <= n; k *= 2) {
			sort(all(sa), [&](int i, int j) {
				if (rk[i] != rk[j])return rk[i] < rk[j];
				else {
					int ri = i + k <= n ? rk[i + k] : -1;
					int rj = j + k <= n ? rk[j + k] : -1;
					return ri < rj;
				}
			});
			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++)rk[i] = tmp[i];
		}
		construct_lcp();
	}


	void construct_lcp() {
		for (int i = 0; i <= n; i++)rklcp[sa[i]] = i;
		int h = 0;
		lcp[0] = 0;
		for (int i = 0; i < n; i++) {
			int j = sa[rklcp[i] - 1];
			if (h > 0)h--;
			while (j + h < n && i + h < n) {
				if (str[j + h] != str[i + h])break;
				h++;
			}
			lcp[rklcp[i] - 1] = h;
		}
		seg.init();
		for (int i = 0; i < n; i++)seg.st(i, lcp[i]);
	}

	pair<int, int> get_lcp(string T, int si, int offset) {
		int i = offset;
		si += offset;
		while (i < T.size() && si < n) {
			if (T[i] != str[si]) {
				return { i,T[i] - str[si] };
			}
			i++;
			si++;
		}
		return { i,0 };
	}

	int search(string T) {
		int ok = 0, ng = n + 1;
		int Llcp = 0;
		while (ng - ok > 1) {
			int mid = (ok + ng) / 2;
			int nlcp = seg.get(ok,mid-1);
			if (Llcp < nlcp)ok = mid;
			else if (Llcp > nlcp)ng = mid;
			else {
				auto p = get_lcp(T, sa[mid], Llcp);
				if (p.second >= 0) {
					ok = mid;
					Llcp = p.first;
				}
				else ng = mid;
			}
		}
		return get_lcp(T,sa[ok],Llcp).first == T.size();
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	string T;
	cin >> T;

	suffixarray sa;
	sa.construct_sa(T);

	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		string P;
		cin >> P;
		puts(sa.search(P));
	}

	return 0;
}


```