#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n) / gcd(n, m)*abs(m);//gl=xy
}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;

struct SuffixArray{
  const string str;
  vector<int>sa;//接尾辞配列
  vector<int>rank;//何番目に小さいか
  vector<int>tmp;

  SuffixArray(const string& s):str(s){//構築 O(N(log N)^2)
    int n=s.size();
    int k=1;
    sa=vector<int>(n+1);
    rank=vector<int>(n+1);
    tmp=vector<int>(n+1);

    for(int i=0;i<=n;++i){
      sa[i]=i;//1文字から構築
      rank[i]=i<n?str[i]:-1;//ランクは文字コードに
    }
    auto comp=[&](int i,int j){//(rank[i],rank[i+k])と(rank[j],rank[j+k])を比較
      if(rank[i]!=rank[j])return rank[i]<rank[j];
      else return (i+k<=n?rank[i+k]:-1)<(j+k<=n?rank[j+k]:-1);
    };
    for(k=1;k<=n;k*=2){//k文字ソートされているところから2k文字でソートする
      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];
    }
  }

  bool search(const string& t){
    int a=0,b=str.size();
    while(b-a>1){
      int c=(a+b)/2;
      if(str.compare(sa[c],t.size(),t)<0)a=c;//strのsa[c]文字目から|T|文字目までとTを比較
      else b=c;
    }
    return str.compare(sa[b],t.size(),t)==0;
  }
};

void solve(){
  string s;
  cin>>s;
  SuffixArray sa(s);
  int q;
  cin>>q;
  while(q--){
    string t;
    cin>>t;
    if(sa.search(t))cout<<1<<"\n";
    else cout<<0<<"\n";
  }
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
  solve();
	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<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n) / gcd(n, m)*abs(m);//gl=xy
}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;

struct SuffixArray{
  const string str;
  vector<int>sa;//接尾辞配列
  vector<int>rank;//何番目に小さいか
  vector<int>tmp;

  SuffixArray(const string& s):str(s){//構築 O(N(log N)^2)
    int n=s.size();
    int k=1;
    sa=vector<int>(n+1);
    rank=vector<int>(n+1);
    tmp=vector<int>(n+1);

    for(int i=0;i<=n;++i){
      sa[i]=i;//1文字から構築
      rank[i]=i<n?str[i]:-1;//ランクは文字コードに
    }
    auto comp=[&](int i,int j){//(rank[i],rank[i+k])と(rank[j],rank[j+k])を比較
      if(rank[i]!=rank[j])return rank[i]<rank[j];
      else return (i+k<=n?rank[i+k]:-1)<(j+k<=n?rank[j+k]:-1);
    };
    for(k=1;k<=n;k*=2){//k文字ソートされているところから2k文字でソートする
      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];
    }
  }

  bool search(const string& t){
    int a=0,b=str.size();
    while(b-a>1){
      int c=(a+b)/2;
      if(str.compare(sa[c],t.size(),t)<0)a=c;//strのsa[c]文字目から|T|文字目までとTを比較
      else b=c;
    }
    return str.compare(sa[b],t.size(),t)==0;
  }
};

void solve(){
  string s;
  cin>>s;
  SuffixArray sa(s);
  int q;
  cin>>q;
  while(q--){
    string t;
    cin>>t;
    if(sa.search(t))cout<<1<<"\n";
    else cout<<0<<"\n";
  }
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
  solve();
	return 0;
}

```