# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)
# pragma warning(disable:4996)

const int MAX_N = 1000000;

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

//(rank[i],rank[i+k])と(rank[j],rank[j+k])を比較
bool compare_sa(int i, int j) {
	if (Rank[i] != Rank[j]) return Rank[i] < Rank[j];
	else {
		int r1 = (i + k <= n ? Rank[i + k] : -1);
		int r2 = (j + k <= n ? Rank[j + k] : -1);
		return r1 < r2;
	}
}

//文字列Sの接尾辞配列（全ての接尾辞を辞書順にソートしたもの）を構築
void construct_sa(string s, int *sa) {
	n = s.length();

	//最初は1文字、ランクは文字コードにすればよい
	for (int i = 0; i <= n; i++) {
		sa[i] = i;
		Rank[i] = (i < n ? s[i] : -1);
	}

	//k文字についてソートされているところから2k文字でソートする
	for (k = 1; k <= n; k *= 2) {
		sort(sa, sa + n + 1, compare_sa);

		//いったんtmpに次のランクを計算し、それからRankに移す
		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(string s, int *sa, string t) {
	int a = 0, b = s.length();
	while (b - a > 1) {
		int c = (a + b) / 2;
		//sのsa[c]文字目から|T|文字とTを比較
		if (s.compare(sa[c], t.length(), t) < 0)a = c;
		else b = c;
	}
	return s.compare(sa[b], t.length(), t) == 0;//0の時一致を表す
}

int Rank2[MAX_N + 1];

//文字列Sとその接尾辞配列saを受け取り、高さ配列をlcpに計算
void construct_lcp(string s, int *sa, int *lcp) {
	int N = s.length();
	for (int i = 0; i <= N; i++)Rank2[sa[i]] = i;

	int h = 0;
	lcp[0] = 0;
	for (int i = 0; i < N; i++) {
		//文字列中での位置iの接尾辞と、接尾辞配列中でその1つ前の接尾辞のLCPを求める
		int j = sa[Rank2[i] - 1];

		//hを先頭の分1減らし、後ろが一致しているだけ増やす
		if (h > 0)h--;
		for (; j + h < N&&i + h < N; h++) {
			if (s[j + h] != s[i + h])break;
		}
		lcp[Rank2[i] - 1] = h;
	}
}

string s, p;
int q;
int sa[MAX_N + 1];
int main() {
	cin >> s >> q;
	construct_sa(s,sa);
	REP(qqq, q) {
		cin >> p;
		cout << contain(s, sa, p) << endl;
	}
}

### 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;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)
# pragma warning(disable:4996)

const int MAX_N = 1000000;

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

//(rank[i],rank[i+k])と(rank[j],rank[j+k])を比較
bool compare_sa(int i, int j) {
	if (Rank[i] != Rank[j]) return Rank[i] < Rank[j];
	else {
		int r1 = (i + k <= n ? Rank[i + k] : -1);
		int r2 = (j + k <= n ? Rank[j + k] : -1);
		return r1 < r2;
	}
}

//文字列Sの接尾辞配列（全ての接尾辞を辞書順にソートしたもの）を構築
void construct_sa(string s, int *sa) {
	n = s.length();

	//最初は1文字、ランクは文字コードにすればよい
	for (int i = 0; i <= n; i++) {
		sa[i] = i;
		Rank[i] = (i < n ? s[i] : -1);
	}

	//k文字についてソートされているところから2k文字でソートする
	for (k = 1; k <= n; k *= 2) {
		sort(sa, sa + n + 1, compare_sa);

		//いったんtmpに次のランクを計算し、それからRankに移す
		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(string s, int *sa, string t) {
	int a = 0, b = s.length();
	while (b - a > 1) {
		int c = (a + b) / 2;
		//sのsa[c]文字目から|T|文字とTを比較
		if (s.compare(sa[c], t.length(), t) < 0)a = c;
		else b = c;
	}
	return s.compare(sa[b], t.length(), t) == 0;//0の時一致を表す
}

int Rank2[MAX_N + 1];

//文字列Sとその接尾辞配列saを受け取り、高さ配列をlcpに計算
void construct_lcp(string s, int *sa, int *lcp) {
	int N = s.length();
	for (int i = 0; i <= N; i++)Rank2[sa[i]] = i;

	int h = 0;
	lcp[0] = 0;
	for (int i = 0; i < N; i++) {
		//文字列中での位置iの接尾辞と、接尾辞配列中でその1つ前の接尾辞のLCPを求める
		int j = sa[Rank2[i] - 1];

		//hを先頭の分1減らし、後ろが一致しているだけ増やす
		if (h > 0)h--;
		for (; j + h < N&&i + h < N; h++) {
			if (s[j + h] != s[i + h])break;
		}
		lcp[Rank2[i] - 1] = h;
	}
}

string s, p;
int q;
int sa[MAX_N + 1];
int main() {
	cin >> s >> q;
	construct_sa(s,sa);
	REP(qqq, q) {
		cin >> p;
		cout << contain(s, sa, p) << endl;
	}
}

```