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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

void buildSA(const string& s, VI& sa, VI& rank){
  int N = SZ(s);
  vector<int> tmp(N+1);
  sa.assign(N+1, 0);
  rank.assign(N+1, 0);
  for(int i=0;i<N+1;++i) sa[i] = i, rank[i] = (i < N? s[i]: -1);

  int h;
  auto comp = [&](int x, int y){
	return rank[x]!=rank[y]? rank[x] < rank[y]
	: (x+h<=N?rank[x+h]:-1) < (y+h<=N?rank[y+h]:-1);
  };
  for(h=1;h<=N;h*=2){
	sort(sa.begin(), sa.end(), comp);
	tmp[sa[0]] = 0;
	for(int i=1;i<=N;++i)
	  tmp[sa[i]] = tmp[sa[i-1]] + (comp(sa[i-1], sa[i])?1:0);
	for(int i=0;i<=N;++i)
	  rank[i] = tmp[i];
  }
}

int findSA(const string& t, const string& p, const vector<int>& sa){
  int a = 0, b = SZ(t), m = SZ(p);
  while(a < b) {
    int c = (a + b) / 2;
    if(strncmp(t.c_str()+sa[c], p.c_str(), m) < 0)
	  a = c+1;
	else
	  b = c;
  }
  return strncmp(t.c_str()+sa[a], p.c_str(), m) == 0 ? sa[a] : -1;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  string text;
  cin >> text;
  VI sa, rank;
  buildSA(text, sa, rank);
  
  int Q; cin >> Q;
  while(Q--){
	string p;
	cin >> p;
	cout << (findSA(text, p, sa) != -1) << endl;
  }

  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>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

void buildSA(const string& s, VI& sa, VI& rank){
  int N = SZ(s);
  vector<int> tmp(N+1);
  sa.assign(N+1, 0);
  rank.assign(N+1, 0);
  for(int i=0;i<N+1;++i) sa[i] = i, rank[i] = (i < N? s[i]: -1);

  int h;
  auto comp = [&](int x, int y){
	return rank[x]!=rank[y]? rank[x] < rank[y]
	: (x+h<=N?rank[x+h]:-1) < (y+h<=N?rank[y+h]:-1);
  };
  for(h=1;h<=N;h*=2){
	sort(sa.begin(), sa.end(), comp);
	tmp[sa[0]] = 0;
	for(int i=1;i<=N;++i)
	  tmp[sa[i]] = tmp[sa[i-1]] + (comp(sa[i-1], sa[i])?1:0);
	for(int i=0;i<=N;++i)
	  rank[i] = tmp[i];
  }
}

int findSA(const string& t, const string& p, const vector<int>& sa){
  int a = 0, b = SZ(t), m = SZ(p);
  while(a < b) {
    int c = (a + b) / 2;
    if(strncmp(t.c_str()+sa[c], p.c_str(), m) < 0)
	  a = c+1;
	else
	  b = c;
  }
  return strncmp(t.c_str()+sa[a], p.c_str(), m) == 0 ? sa[a] : -1;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  string text;
  cin >> text;
  VI sa, rank;
  buildSA(text, sa, rank);
  
  int Q; cin >> Q;
  while(Q--){
	string p;
	cin >> p;
	cout << (findSA(text, p, sa) != -1) << endl;
  }

  return 0;
}
```