#include <bits/stdc++.h>
using namespace std;

struct SuffixArray{
	string s;
	vector<int> sa;

	int operator[](int i) const{ return sa[i]; }

	SuffixArray(const string &t) : s(t),sa(s.size() + 1){
		s += '$';
		int n = s.size();
		iota(sa.begin(),sa.end(),0);
		sort(sa.begin(),sa.end(),[&](int a,int b){ return s[a] < s[b]; });
		vector<int> rnk(s.begin(),s.end()),cnt(n),nxt(n);
		for(int k = 1;k < n;k <<= 1){
			nxt[sa[0]] = 0;
			for(int i = 1;i < n;i++){
				nxt[sa[i]] = (rnk[sa[i - 1]] == rnk[sa[i]]
				&& rnk[(sa[i - 1] + k / 2) % n] == rnk[(sa[i] + k / 2) % n])
				? nxt[sa[i - 1]] : i;
			}
			rnk.swap(nxt);

			iota(cnt.begin(),cnt.end(),0);
			for(int i = 0;i < n;i++){
				int s1 = (sa[i] - k + n) % n;
				nxt[cnt[rnk[s1]]++] = s1;
			}
			sa.swap(nxt);
		}
	}

	inline int lower_bound(const string &t) const{
		return partition_point(sa.begin(),sa.end(),[&](int x){
			return s.compare(x,t.length(),t) < 0;
		}) - sa.begin();
	}

	int upper_bound(string &t) const{
		t.back()++;
		int ret = lower_bound(t);
		t.back()--;
		return ret;
	}

	inline int count(string &t) const{
		return upper_bound(t) - lower_bound(t);
	}
};

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string t;
	int q;
	cin >> t >> q;
	SuffixArray sa(t);
	for(int i = 0;i < q;i++){
		string p;
		cin >> p;
		cout << !!sa.count(p) << endl;
	}
}

### Prompt

Develop a solution in Cpp 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 <bits/stdc++.h>
using namespace std;

struct SuffixArray{
	string s;
	vector<int> sa;

	int operator[](int i) const{ return sa[i]; }

	SuffixArray(const string &t) : s(t),sa(s.size() + 1){
		s += '$';
		int n = s.size();
		iota(sa.begin(),sa.end(),0);
		sort(sa.begin(),sa.end(),[&](int a,int b){ return s[a] < s[b]; });
		vector<int> rnk(s.begin(),s.end()),cnt(n),nxt(n);
		for(int k = 1;k < n;k <<= 1){
			nxt[sa[0]] = 0;
			for(int i = 1;i < n;i++){
				nxt[sa[i]] = (rnk[sa[i - 1]] == rnk[sa[i]]
				&& rnk[(sa[i - 1] + k / 2) % n] == rnk[(sa[i] + k / 2) % n])
				? nxt[sa[i - 1]] : i;
			}
			rnk.swap(nxt);

			iota(cnt.begin(),cnt.end(),0);
			for(int i = 0;i < n;i++){
				int s1 = (sa[i] - k + n) % n;
				nxt[cnt[rnk[s1]]++] = s1;
			}
			sa.swap(nxt);
		}
	}

	inline int lower_bound(const string &t) const{
		return partition_point(sa.begin(),sa.end(),[&](int x){
			return s.compare(x,t.length(),t) < 0;
		}) - sa.begin();
	}

	int upper_bound(string &t) const{
		t.back()++;
		int ret = lower_bound(t);
		t.back()--;
		return ret;
	}

	inline int count(string &t) const{
		return upper_bound(t) - lower_bound(t);
	}
};

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string t;
	int q;
	cin >> t >> q;
	SuffixArray sa(t);
	for(int i = 0;i < q;i++){
		string p;
		cin >> p;
		cout << !!sa.count(p) << endl;
	}
}

```