#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<ld> vld;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;  // 小さい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;     // 大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); ++i)
#define TS to_string
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define endl "\n"

ll INF = 1e9;
ll MOD = 1000000007;
ll LINF = 1e18;
ld EPS = 1e-9;
ld PI = M_PI;
vll dx = {1, 0, -1, 0, 1, -1, -1, 1};
vll dy = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b;}     //最小公倍数

void yes(){ cout << "Yes" << endl;}
void no(){ cout << "No" << endl;}

//-----------------------------------------
class suffix_array{
  private:
    string s; // suffix_array の対象
    ll n, k; // n : sの長さ
    vll sa, tmp, rank; // sa : sufffixの開始位置

  public:

    suffix_array(string &str){
      s = str;
      n = s.size();

      sa.resize(n+1);
      rank.resize(n+1);
      tmp.resize(n+1);

      for(ll i=0;i<=n;i++){
        sa[i] = i;
        rank[i] = i < n ? (ll)s[i] : -1;
      }

      auto compare_sa = [&](ll i, ll j){
        if(rank[i] != rank[j]) return rank[i] < rank[j];
        else{
          ll ri = i + k <= n ? rank[i + k] : -1;
          ll rj = j + k <= n ? rank[j + k] : -1;
          return ri < rj;
        }
      };

      for(k=1;k<=n;k*=2){
        sort(sa.begin(),sa.end(), compare_sa);

        tmp[sa[0]] = 0;

        for(ll i=1;i<=n;i++){
          tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
        }
        for(ll i=0;i<=n;i++){
          rank[i] = tmp[i];
        }
      }
    }

    // [lb,ub) の各要素はtを部分文字列として含む
    pll range(string &t){
      ll m = t.size();
      ll ub, lb;
      ll lef, rig, mid;
      
      lef = 0; rig = n+1; // sa[0]は空 サイズがn+1

      while(rig - lef > 1){
        mid = (lef + rig) / 2; 
        string subs = s.substr(sa[mid],m);
        if(t <= subs) rig = mid;
        else lef = mid;
      }
      lb = rig;

      lef = 0; rig = n+1; // sa[0]は空 サイズがn+1

      while(rig - lef > 1){
        mid = (lef + rig) / 2;
        string subs = s.substr(sa[mid],m);
        if(t < subs) rig = mid;
        else lef = mid;
      }
      ub = rig;

      return make_pair(lb, ub);
    }

    // 何箇所tを含むか
    ll cnt(string &t){
      pll res = range(t);
      return res.second - res.first;
    }
};
//-----------------------------------------
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  string t;
  cin >> t;

  suffix_array sarray(t);

  ll q;
  cin >> q;
  REP(i,q){
    string p;
    cin >> p;
    ll a = sarray.cnt(p);
    cout << (a != 0) <<endl;
  }


    
  return 0;
}



### Prompt

Develop a solution in cpp to the problem described below:

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;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<ld> vld;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;  // 小さい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;     // 大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); ++i)
#define TS to_string
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define endl "\n"

ll INF = 1e9;
ll MOD = 1000000007;
ll LINF = 1e18;
ld EPS = 1e-9;
ld PI = M_PI;
vll dx = {1, 0, -1, 0, 1, -1, -1, 1};
vll dy = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b;}     //最小公倍数

void yes(){ cout << "Yes" << endl;}
void no(){ cout << "No" << endl;}

//-----------------------------------------
class suffix_array{
  private:
    string s; // suffix_array の対象
    ll n, k; // n : sの長さ
    vll sa, tmp, rank; // sa : sufffixの開始位置

  public:

    suffix_array(string &str){
      s = str;
      n = s.size();

      sa.resize(n+1);
      rank.resize(n+1);
      tmp.resize(n+1);

      for(ll i=0;i<=n;i++){
        sa[i] = i;
        rank[i] = i < n ? (ll)s[i] : -1;
      }

      auto compare_sa = [&](ll i, ll j){
        if(rank[i] != rank[j]) return rank[i] < rank[j];
        else{
          ll ri = i + k <= n ? rank[i + k] : -1;
          ll rj = j + k <= n ? rank[j + k] : -1;
          return ri < rj;
        }
      };

      for(k=1;k<=n;k*=2){
        sort(sa.begin(),sa.end(), compare_sa);

        tmp[sa[0]] = 0;

        for(ll i=1;i<=n;i++){
          tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
        }
        for(ll i=0;i<=n;i++){
          rank[i] = tmp[i];
        }
      }
    }

    // [lb,ub) の各要素はtを部分文字列として含む
    pll range(string &t){
      ll m = t.size();
      ll ub, lb;
      ll lef, rig, mid;
      
      lef = 0; rig = n+1; // sa[0]は空 サイズがn+1

      while(rig - lef > 1){
        mid = (lef + rig) / 2; 
        string subs = s.substr(sa[mid],m);
        if(t <= subs) rig = mid;
        else lef = mid;
      }
      lb = rig;

      lef = 0; rig = n+1; // sa[0]は空 サイズがn+1

      while(rig - lef > 1){
        mid = (lef + rig) / 2;
        string subs = s.substr(sa[mid],m);
        if(t < subs) rig = mid;
        else lef = mid;
      }
      ub = rig;

      return make_pair(lb, ub);
    }

    // 何箇所tを含むか
    ll cnt(string &t){
      pll res = range(t);
      return res.second - res.first;
    }
};
//-----------------------------------------
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  string t;
  cin >> t;

  suffix_array sarray(t);

  ll q;
  cin >> q;
  REP(i,q){
    string p;
    cin >> p;
    ll a = sarray.cnt(p);
    cout << (a != 0) <<endl;
  }


    
  return 0;
}



```