#include "bits/stdc++.h"
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define IOS std::cin.tie(0),std::ios::sync_with_stdio(false)

namespace idaten {

	using namespace std;
	using ll = int_fast64_t;
	using ull = uint_fast64_t;
	using P = std::pair<int64_t, int64_t>;
	template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
	template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
	template<class Type>struct is_vector : std::false_type {};
	template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
	template <typename T> inline std::ostream& operator << (std::ostream& out, const std::vector<T>& v) {
		if (v.empty())return out;
		constexpr bool is_vector_v = is_vector<T>::value;
		if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
		else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
		return out;
	}
	inline void put() {}
	template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
	template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
	inline void putn() {}
	template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }
	int get_front(vector<int>& t, vector<int>& sum, vector<int>& ch, int num) {
		int res = sum[t[num]];
		res += ch[t[num]]++;
		return res;
	}

	int get_back(vector<int>& t, vector<int>& sum, vector<int>& ct, int num) {
		int res = sum[t[num] + 1] - 1;
		res -= ct[t[num]]++;
		return res;
	}

	void induced_sort(vector<int>& t, vector<int>& table, vector<int>& sum, vector<int>& ls, int ma) {
		int n = t.size();
		vector<int> ch(ma + 1, 0), ct(ma + 1, 0);
		for (int i = 0; i < n; ++i) {
			if (table[i] >= 0) {
				int ind = table[i] - 1;
				if (ind >= 0 && ls[ind]) {
					int d = get_front(t, sum, ch, ind);
					table[d] = ind;
				}
			}
		}
		for (int i = n - 1; i >= 0; --i) {
			if (table[i] >= 0) {
				int ind = table[i] - 1;
				if (ind >= 0 && !ls[ind]) {
					int d = get_back(t, sum, ct, ind);
					table[d] = ind;
				}
			}
		}
	}

	bool is_lms(vector<int>& ls, int ind) {
		return ind > 0 && ls[ind - 1] && !ls[ind];
	}

	template<typename T>
	vector<T> substr(vector<T> v, int a, int b) { // v[a,b)
		a = max(0, a);
		b = min(v.size() - 1, b);
		vector<T> res(max(0, b - a));
		for (int i = a; i < b; i++) {
			res[i - a] = v[i];
		}
		return res;
	}

	vector<int> sais(vector<int>& s) {
		int n = s.size();
		if (n == 1) {
			return vector<int>(1, 0);
		}
		int m = *min_element(s.begin(), s.end());
		if (m != 1) { // 最小値が1となるように変換
			for (int i = 0; i < n; ++i) {
				s[i] -= m - 1;
			}
		}
		int sent = 0; // 番兵が0
		vector<int> t = s;
		t.push_back(sent);
		n++;
		vector<int> ls(n); // 1がl,0がs
		ls.back() = 0;
		for (int i = n - 2; i >= 0; --i) {
			if (t[i] == t[i + 1]) {
				ls[i] = ls[i + 1];
			} else {
				ls[i] = t[i] > t[i + 1];
			}
		}
		vector<int> lms;
		for (int i = 1; i < n; ++i) {
			if (ls[i - 1] && !ls[i]) {
				lms.push_back(i);
			}
		}
		int ma = *max_element(s.begin(), s.end());
		vector<int> cnt(ma + 1, 0);
		for (auto&& v : t) {
			cnt[v]++;
		}
		vector<int> sum(cnt.size() + 1);
		sum[0] = 0;
		for (int i = 0; i < cnt.size(); ++i) {
			sum[i + 1] = sum[i] + cnt[i];
		}
		vector<int> table(n, -1), ch(ma + 1, 0);
		for (int i = (int)lms.size() - 1; i >= 0; --i) {
			int ind = lms[i];
			int d = get_back(t, sum, ch, ind);
			table[d] = lms[i];
		}
		induced_sort(t, table, sum, ls, ma);
		//sorted lms-substring
		vector<int> nt(lms.size());
		int cn = 0;
		vector<int> lms_index(n, -1); // iがlmsのうち先頭から何番目に現れるか
		for (int i = 0; i < n; ++i) {
			if (is_lms(ls, i)) {
				lms_index[i] = cn++;
			}
		}
		cn = 1;
		int sub = 0, preind = -1;
		for (int i = 0; i < n; ++i) { // lms-substringを復元
			int ind = table[i];
			if (is_lms(ls, ind)) {
				if (cn > 1) {
					int a = lms[preind];
					int b = lms[min<int>(preind + 1, lms.size() - 1)];
					int c = lms[lms_index[ind]];
					int d = lms[min<int>(lms_index[ind] + 1, lms.size() - 1)];
					int pre_len = b - a;
					int post_len = d - c;
					if (pre_len != post_len) {
						sub--;
					} else {
						for (int j = 0; j < pre_len; j++) {
							if (t[j + a] != t[j + c]) {
								sub--;
								break;
							}
						}
					}
					sub++;
				}
				nt[lms_index[ind]] = cn - sub;
				preind = lms_index[ind];
				cn++;
			}
		}
		// ntのSAを求めるs
		auto lms_sa = sais(nt);
		std::fill(ch.begin(), ch.end(), 0);
		std::fill(table.begin(), table.end(), 0);
		for (int i = (int)lms_sa.size() - 1; i >= 0; --i) {
			int ind = lms[lms_sa[i]];
			int d = get_back(t, sum, ch, ind);
			table[d] = ind;
		}
		induced_sort(t, table, sum, ls, ma);
		vector<int> res(n - 1);
		for (int i = 0; i < n - 1; ++i) {
			res[i] = table[i + 1];
		}
		return res;
	}

	void sais_rec(vector<int>& s) {}

	vector<int> stovi(string& s) {
		int n = s.size();
		vector<int> res(n);
		char mi = *min_element(s.begin(), s.end());
		for (int i = 0; i < n; i++) {
			res[i] = s[i] - mi + 1;
		}
		return res;
	}

	int find_begin_naive(string& s, vector<int>& sa, string& str) {
		int ng = -1, ok = sa.size();
		int l = str.size();
		while (abs(ng - ok) > 1) {
			int mid = (ng + ok) / 2;
			int suffix_ind = sa[mid];
			int r = min<int>(l, s.size() - suffix_ind);
			string suffix = s.substr(suffix_ind, r);
			if (suffix >= str) {
				ok = mid;
			} else {
				ng = mid;
			}
		}
		return ok;
	}

	int find_end_naive(string& s, vector<int>& sa, string& str) {
		int ok = -1, ng = sa.size();
		int l = str.size();
		while (abs(ng - ok) > 1) {
			int mid = (ng + ok) / 2;
			int suffix_ind = sa[mid];
			int r = min<int>(l, s.size() - suffix_ind);
			string suffix = s.substr(suffix_ind, r);
			if (suffix <= str) {
				ok = mid;
			} else {
				ng = mid;
			}
		}
		return ok;
	}

	int count(string& s, vector<int>& sa, string& str) {
		int beg = find_begin_naive(s, sa, str);
		int en = find_end_naive(s, sa, str);
		return en - beg + 1;
	}

	void solve() {
		IOS; 
		string t;
		cin >> t;
		auto vi = stovi(t);
		auto sa = sais(vi);
		int q;
		cin >> q;
		REP(loop, q) {
			string p;
			cin >> p;
			int c = count(t, sa, p);
			put(!!c);
		}
		
	}
} // namespace idaten

int main() {
	idaten::solve();
	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 Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define IOS std::cin.tie(0),std::ios::sync_with_stdio(false)

namespace idaten {

	using namespace std;
	using ll = int_fast64_t;
	using ull = uint_fast64_t;
	using P = std::pair<int64_t, int64_t>;
	template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
	template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
	template<class Type>struct is_vector : std::false_type {};
	template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
	template <typename T> inline std::ostream& operator << (std::ostream& out, const std::vector<T>& v) {
		if (v.empty())return out;
		constexpr bool is_vector_v = is_vector<T>::value;
		if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
		else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
		return out;
	}
	inline void put() {}
	template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
	template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
	inline void putn() {}
	template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }
	int get_front(vector<int>& t, vector<int>& sum, vector<int>& ch, int num) {
		int res = sum[t[num]];
		res += ch[t[num]]++;
		return res;
	}

	int get_back(vector<int>& t, vector<int>& sum, vector<int>& ct, int num) {
		int res = sum[t[num] + 1] - 1;
		res -= ct[t[num]]++;
		return res;
	}

	void induced_sort(vector<int>& t, vector<int>& table, vector<int>& sum, vector<int>& ls, int ma) {
		int n = t.size();
		vector<int> ch(ma + 1, 0), ct(ma + 1, 0);
		for (int i = 0; i < n; ++i) {
			if (table[i] >= 0) {
				int ind = table[i] - 1;
				if (ind >= 0 && ls[ind]) {
					int d = get_front(t, sum, ch, ind);
					table[d] = ind;
				}
			}
		}
		for (int i = n - 1; i >= 0; --i) {
			if (table[i] >= 0) {
				int ind = table[i] - 1;
				if (ind >= 0 && !ls[ind]) {
					int d = get_back(t, sum, ct, ind);
					table[d] = ind;
				}
			}
		}
	}

	bool is_lms(vector<int>& ls, int ind) {
		return ind > 0 && ls[ind - 1] && !ls[ind];
	}

	template<typename T>
	vector<T> substr(vector<T> v, int a, int b) { // v[a,b)
		a = max(0, a);
		b = min(v.size() - 1, b);
		vector<T> res(max(0, b - a));
		for (int i = a; i < b; i++) {
			res[i - a] = v[i];
		}
		return res;
	}

	vector<int> sais(vector<int>& s) {
		int n = s.size();
		if (n == 1) {
			return vector<int>(1, 0);
		}
		int m = *min_element(s.begin(), s.end());
		if (m != 1) { // 最小値が1となるように変換
			for (int i = 0; i < n; ++i) {
				s[i] -= m - 1;
			}
		}
		int sent = 0; // 番兵が0
		vector<int> t = s;
		t.push_back(sent);
		n++;
		vector<int> ls(n); // 1がl,0がs
		ls.back() = 0;
		for (int i = n - 2; i >= 0; --i) {
			if (t[i] == t[i + 1]) {
				ls[i] = ls[i + 1];
			} else {
				ls[i] = t[i] > t[i + 1];
			}
		}
		vector<int> lms;
		for (int i = 1; i < n; ++i) {
			if (ls[i - 1] && !ls[i]) {
				lms.push_back(i);
			}
		}
		int ma = *max_element(s.begin(), s.end());
		vector<int> cnt(ma + 1, 0);
		for (auto&& v : t) {
			cnt[v]++;
		}
		vector<int> sum(cnt.size() + 1);
		sum[0] = 0;
		for (int i = 0; i < cnt.size(); ++i) {
			sum[i + 1] = sum[i] + cnt[i];
		}
		vector<int> table(n, -1), ch(ma + 1, 0);
		for (int i = (int)lms.size() - 1; i >= 0; --i) {
			int ind = lms[i];
			int d = get_back(t, sum, ch, ind);
			table[d] = lms[i];
		}
		induced_sort(t, table, sum, ls, ma);
		//sorted lms-substring
		vector<int> nt(lms.size());
		int cn = 0;
		vector<int> lms_index(n, -1); // iがlmsのうち先頭から何番目に現れるか
		for (int i = 0; i < n; ++i) {
			if (is_lms(ls, i)) {
				lms_index[i] = cn++;
			}
		}
		cn = 1;
		int sub = 0, preind = -1;
		for (int i = 0; i < n; ++i) { // lms-substringを復元
			int ind = table[i];
			if (is_lms(ls, ind)) {
				if (cn > 1) {
					int a = lms[preind];
					int b = lms[min<int>(preind + 1, lms.size() - 1)];
					int c = lms[lms_index[ind]];
					int d = lms[min<int>(lms_index[ind] + 1, lms.size() - 1)];
					int pre_len = b - a;
					int post_len = d - c;
					if (pre_len != post_len) {
						sub--;
					} else {
						for (int j = 0; j < pre_len; j++) {
							if (t[j + a] != t[j + c]) {
								sub--;
								break;
							}
						}
					}
					sub++;
				}
				nt[lms_index[ind]] = cn - sub;
				preind = lms_index[ind];
				cn++;
			}
		}
		// ntのSAを求めるs
		auto lms_sa = sais(nt);
		std::fill(ch.begin(), ch.end(), 0);
		std::fill(table.begin(), table.end(), 0);
		for (int i = (int)lms_sa.size() - 1; i >= 0; --i) {
			int ind = lms[lms_sa[i]];
			int d = get_back(t, sum, ch, ind);
			table[d] = ind;
		}
		induced_sort(t, table, sum, ls, ma);
		vector<int> res(n - 1);
		for (int i = 0; i < n - 1; ++i) {
			res[i] = table[i + 1];
		}
		return res;
	}

	void sais_rec(vector<int>& s) {}

	vector<int> stovi(string& s) {
		int n = s.size();
		vector<int> res(n);
		char mi = *min_element(s.begin(), s.end());
		for (int i = 0; i < n; i++) {
			res[i] = s[i] - mi + 1;
		}
		return res;
	}

	int find_begin_naive(string& s, vector<int>& sa, string& str) {
		int ng = -1, ok = sa.size();
		int l = str.size();
		while (abs(ng - ok) > 1) {
			int mid = (ng + ok) / 2;
			int suffix_ind = sa[mid];
			int r = min<int>(l, s.size() - suffix_ind);
			string suffix = s.substr(suffix_ind, r);
			if (suffix >= str) {
				ok = mid;
			} else {
				ng = mid;
			}
		}
		return ok;
	}

	int find_end_naive(string& s, vector<int>& sa, string& str) {
		int ok = -1, ng = sa.size();
		int l = str.size();
		while (abs(ng - ok) > 1) {
			int mid = (ng + ok) / 2;
			int suffix_ind = sa[mid];
			int r = min<int>(l, s.size() - suffix_ind);
			string suffix = s.substr(suffix_ind, r);
			if (suffix <= str) {
				ok = mid;
			} else {
				ng = mid;
			}
		}
		return ok;
	}

	int count(string& s, vector<int>& sa, string& str) {
		int beg = find_begin_naive(s, sa, str);
		int en = find_end_naive(s, sa, str);
		return en - beg + 1;
	}

	void solve() {
		IOS; 
		string t;
		cin >> t;
		auto vi = stovi(t);
		auto sa = sais(vi);
		int q;
		cin >> q;
		REP(loop, q) {
			string p;
			cin >> p;
			int c = count(t, sa, p);
			put(!!c);
		}
		
	}
} // namespace idaten

int main() {
	idaten::solve();
	return 0;
}


```