#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <sstream>

#define rep(i, a) REP(i, 0, a)
#define REP(i, a, b) for(int i = a; i < b; ++i)
#define rrep(i, a) RREP(i, a, 0)
#define RREP(i, a, b) for(int i = a; i >= b; --i)
#define repll(i, a) REPLL(i, 0, a)
#define REPLL(i, a, b) for(ll i = a; i < b; ++i)
#define rrepll(i, a) RREPLL(i, a, 0)
#define RREPLL(i, a, b) for(ll i = a; i >= b; --i)

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> P;
typedef std::pair<int, P> PP;
const double PI = 3.14159265358979323846;
const double esp = 1e-9;
const int infi = (int)1e+9 + 10;
const ll infll = (ll)1e+18 + 10;

const int max = 1000005;

std::string text;
int textSize, k = 1;
int rank[max + 1], tmp[max + 1], sa[max + 1];

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

void construct_sa(){
	textSize = text.size();
	rep(i, textSize + 1){
		sa[i] = i;
		rank[i] = (i < textSize ? text[i] : -1);
	}

	for (; k <= textSize; k *= 2){
		std::sort(sa, sa + textSize + 1, compare_sa);

		tmp[sa[0]] = 0;
		REP(j, 1, textSize + 1)tmp[sa[j]] = tmp[sa[j - 1]] + (compare_sa(sa[j - 1], sa[j]) ? 1 : 0);
		rep(j, textSize + 1)rank[j] = tmp[j];
	}
}

bool find(std::string t){
	int l = 0, r = text.size();
	while (l <= r){
		int m = (l + r) / 2;
		if (text.compare(sa[m], t.size(), t) < 0)l = m + 1;
		else r = m - 1;
	}
	return (text.compare(sa[r + 1], t.size(), t) == 0);
}

int n;

int main(){
	std::cin >> text >> n;
	construct_sa();
	rep(i, n){
		std::string str;
		std::cin >> str;
		std::cout << (find(str) ? 1 : 0) << std::endl;
	}

	return 0;
}
### Prompt

In Cpp, your task is to solve 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 <algorithm>
#include <string>
#include <vector>
#include <list>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <sstream>

#define rep(i, a) REP(i, 0, a)
#define REP(i, a, b) for(int i = a; i < b; ++i)
#define rrep(i, a) RREP(i, a, 0)
#define RREP(i, a, b) for(int i = a; i >= b; --i)
#define repll(i, a) REPLL(i, 0, a)
#define REPLL(i, a, b) for(ll i = a; i < b; ++i)
#define rrepll(i, a) RREPLL(i, a, 0)
#define RREPLL(i, a, b) for(ll i = a; i >= b; --i)

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> P;
typedef std::pair<int, P> PP;
const double PI = 3.14159265358979323846;
const double esp = 1e-9;
const int infi = (int)1e+9 + 10;
const ll infll = (ll)1e+18 + 10;

const int max = 1000005;

std::string text;
int textSize, k = 1;
int rank[max + 1], tmp[max + 1], sa[max + 1];

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

void construct_sa(){
	textSize = text.size();
	rep(i, textSize + 1){
		sa[i] = i;
		rank[i] = (i < textSize ? text[i] : -1);
	}

	for (; k <= textSize; k *= 2){
		std::sort(sa, sa + textSize + 1, compare_sa);

		tmp[sa[0]] = 0;
		REP(j, 1, textSize + 1)tmp[sa[j]] = tmp[sa[j - 1]] + (compare_sa(sa[j - 1], sa[j]) ? 1 : 0);
		rep(j, textSize + 1)rank[j] = tmp[j];
	}
}

bool find(std::string t){
	int l = 0, r = text.size();
	while (l <= r){
		int m = (l + r) / 2;
		if (text.compare(sa[m], t.size(), t) < 0)l = m + 1;
		else r = m - 1;
	}
	return (text.compare(sa[r + 1], t.size(), t) == 0);
}

int n;

int main(){
	std::cin >> text >> n;
	construct_sa();
	rep(i, n){
		std::string str;
		std::cin >> str;
		std::cout << (find(str) ? 1 : 0) << std::endl;
	}

	return 0;
}
```