#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

class SuffixArray {
  template <typename T>
  class RangeMinmaxQuery {
    template <typename C>
    struct Compare { bool operator()(const C &a, const C &b) const { return a < b; } };
    template <typename S>
    class SparseTable {
      Compare<S> comp;
      vector<vector<int>> st;
      vector<int> lookup;
      vector<S>   origin;

      public:
      SparseTable(void) {}
      SparseTable(const vector<S> &v) { init(v); }
      void init(const vector<S> &v) {
        origin = v;
        int lg_size = 0, v_size = v.size();
        while ((1 << lg_size) <= v_size) ++lg_size;
        st.assign((1 << lg_size), vector<int>(lg_size));
        for (int i = 0; i < v_size; ++i) st[i][0] = i;
        for (int j = 1; j < lg_size; ++j) {
          for (int i = 0; i + (1 << j) <= (1 << lg_size); ++i) {
            int l = st[i][j - 1], r = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = comp(v[r], v[l]) ? r : l;
          }
        }
        lookup.assign(v_size + 1, 0);
        for (int i = 2; i <= v_size; ++i) lookup[i] = lookup[i >> 1] + 1;
      }
      S query(int l, int r) const {
        int lg_size = lookup[r - l];
        S   lret = origin[st[l][lg_size]], rret = origin[st[r - (1 << lg_size)][lg_size]];
        return comp(rret, lret) ? rret : lret;
      }
      int query_index(int l, int r) const {
        int lg_size = lookup[r - l];
        int lidx = st[l][lg_size], ridx = st[r - (1 << lg_size)][lg_size];
        return comp(origin[ridx], origin[lidx]) ? ridx : lidx;
      }
      int size(void) const { return st.size(); }
    };
    Compare<T> comp;
    int v_size, bl_size, bl_num;
    SparseTable<pair<T, int>> st;
    vector<int> bit;
    vector<T>   origin;
    static int lsb(const unsigned bit) {
      static constexpr int table[32] = {0,  1,  28, 2,  29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4,  8,
                                        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6,  11, 5,  10, 9};
      return table[((bit & -bit) * 0x077CB531) >> 27];
    }
    int block_query(const int l, const int r, const int bl_n) const {
      int bl_l = bl_size * bl_n, x = bit[r] & ~((1 << (l - bl_l)) - 1);
      return x ? bl_l + lsb(x) : r;
    }

    public:
    RangeMinmaxQuery(void) {}
    RangeMinmaxQuery(const vector<T> &v) { init(v); }
    void init(const vector<T> &v) {
      origin = v, v_size = v.size(), bl_size = 0;
      while ((1 << bl_size) < v_size) ++bl_size;
      bl_size = max(1, bl_size >> 1);
      bl_num  = (v_size + bl_size - 1) / bl_size;
      vector<pair<T, int>> bl_v(bl_num, {numeric_limits<T>::max(), INT_MAX});
      for (int i = 0, j = 0; i < v_size; ++i, j = i / bl_size) if (comp(v[i], bl_v[j].first)) bl_v[j] = {v[i], i};
      st.init(move(bl_v));
      bit.assign(v_size, 0);
      for (int i = 0, l = 0; i < bl_num; ++i, l += bl_size) {
        vector<int> helper(bl_size), inc(bl_size);
        for (int j = 0, now = -1, r = min(bl_size, v_size - l); j < r; ++j) {
          while (now >= 0 && !comp(v[l + inc[now]], v[l + j])) --now;
          helper[j]  = now >= 0 ? inc[now] : -1;
          inc[++now] = j;
        }
        for (int j = 0, r = min(bl_size, v_size - l); j < r; ++j) bit[l + j] = helper[j] >= 0 ? bit[l + helper[j]] | (1 << helper[j]) : 0;
      }
    }
    T   query(const int l, const int r) const { return origin[query_index(l, r)]; }
    int query_index(int l, int r) const {
      int lbl_n = l / bl_size, rbl_n = --r / bl_size, lbl_p = l % bl_size, rbl_p = r % bl_size;
      if (lbl_n == rbl_n) return block_query(l, r, lbl_n);
      int lret = lbl_p > 0 ? block_query(l, l - lbl_p + bl_size - 1, lbl_n++) : l;
      int rlet = rbl_p < bl_size - 1 ? block_query(r - rbl_p, r, rbl_n--) : r;
      int ret  = comp(origin[rlet], origin[lret]) ? rlet : lret;
      if (lbl_n <= rbl_n) {
        pair<T, int> mret = st.query(lbl_n, rbl_n + 1);
        if (comp(mret.first, origin[ret])) ret = mret.second;
      }
      return ret;
    }
    int size(void) const { return v_size; }
  };
  vector<int>::iterator arr;
  vector<int> string_to_vector(const string &s) const { return vector<int>(s.begin(), s.end()); }
  bool lms(const int i, const vector<bool> &ltype) const { return i > 0 && !ltype[i] && ltype[i - 1]; }
  vector<int> get_count(const vector<int>::const_iterator &str, const int len, const int chnum) const {
    vector<int> cnt(chnum + 1);
    for (int i = 0; i < len; ++i) ++cnt[str[i]];
    return cnt;
  }
  vector<int> get_buckets(const vector<int> &cnt, const bool back) const {
    int clen = cnt.size(), sum = 1;
    vector<int> buckets(clen);
    for (int i = 0; i < clen; ++i) {
      sum += cnt[i];
      buckets[i] = back ? sum : sum - cnt[i];
    }
    return buckets;
  }
  void induced_sort_ls(const vector<int>::const_iterator &str, const int len, const vector<bool> &ltype, const vector<int> &cnt, vector<int> &buckets) {
    int prev;
    buckets = get_buckets(cnt, false);
    for (int i = 0; i < len; ++i) {
      if ((prev = arr[i] - 1) >= 0 && ltype[prev]) arr[buckets[str[prev]]++] = prev;
    }
    buckets = get_buckets(cnt, true);
    for (int i = len - 1; i >= 0; --i) {
      if ((prev = arr[i] - 1) >= 0 && !ltype[prev]) arr[--buckets[str[prev]]] = prev;
    }
  }
  void sa_is(const vector<int>::const_iterator &str, int len, const int chmax) {
    fill(arr, arr + len, -1);
    vector<bool> ltype(len);
    ltype[len - 2] = true;
    for (int i = len - 3; i >= 0; --i) ltype[i] = str[i] > str[i + 1] || (str[i] == str[i + 1] && ltype[i + 1] == true);
    vector<int> cnt = get_count(str, len - 1, chmax), buckets = get_buckets(cnt, true);
    arr[0] = len - 1;
    for (int i = 1; i < len - 1; ++i) if (lms(i, ltype)) arr[--buckets[str[i]]] = i;
    induced_sort_ls(str, len, ltype, cnt, buckets);
    int lms_num = 0, now = -1, prev = -1, name = -1, mid = len / 2;
    for (int i = 0; i < len; ++i) if (lms(arr[i], ltype)) arr[lms_num++] = arr[i];
    fill(arr + lms_num, arr + len, -1);
    for (int i = 0; i < lms_num; ++i) {
      prev = now; now  = arr[i];
      for (int nowp = now, prevp = prev; nowp < len && prevp < len; ++nowp, ++prevp) {
        int lmscheck = (lms(nowp, ltype)) + lms(prevp, ltype);
        if (prev == -1 || str[nowp] != str[prevp] || lmscheck & 1) { ++name; break; }
        if (lmscheck && nowp > now) break;
      }
      arr[lms_num + now / 2] = name;
    }
    for (int i = len - 1, j = i; i >= lms_num; --i) if (arr[i] >= 0) arr[j--] = arr[i];
    vector<int>::iterator arr2 = arr + len - lms_num;
    if (lms_num == name + 1) {
      for (int i = 0; i < lms_num; ++i) arr[arr2[i]] = i;
    } else {
      sa_is(arr2, lms_num, name);
    }
    for (int i = 0, j = 0; i < len; ++i) if (lms(i, ltype)) arr2[j++] = i;
    for (int i = 0; i < lms_num; ++i) arr[i] = arr2[arr[i]];
    fill(arr + lms_num, arr + len, -1);
    buckets = get_buckets(cnt, true);
    for (int i = lms_num - 1; i > 0; --i) {
      int x = arr[i];
      arr[i] = -1;
      arr[--buckets[str[x]]] = x;
    }
    induced_sort_ls(str, len, ltype, cnt, buckets);
  }
  void init_lcp(const vector<int> &v) {
    const int len = sa.size() - 1;
    lcp.assign(len + 1, 0);
    lcp[len] = len;
    vector<int> rank(len + 1);
    for (int i = 0; i <= len; ++i) rank[sa[i]] = i;
    int h = 0;
    for (int now = 0; now < len; ++now) {
      int prev = sa[rank[now] - 1];
      if (h > 0) --h;
      for (; now + h < len && prev + h < len && v[now + h] == v[prev + h]; ++h);
      lcp[rank[now] - 1] = h;
    }
    rmq.init(lcp);
  }
  pair<int, int> direct_compare(const vector<int> &v, int pos, int h = 0) const {
    int olen = intv.size() - pos - 1, vlen = v.size(), comp;
    pos += h;
    for (int r = min(olen, vlen); h < r && intv[pos] == v[h]; ++h, ++pos);
    if (h == vlen) comp = -1;
    else if (h == olen) comp = 1;
    else comp = (intv[pos] < v[h]) - (intv[pos] > v[h]);
    return {comp, h};
  }
  RangeMinmaxQuery<int> rmq;

  public:
  vector<int> sa, lcp, intv;

  SuffixArray(void) {}
  SuffixArray(const string &s) { init(s); }
  SuffixArray(vector<int> &v) { init(v); }
  void init(const string &s) { init(string_to_vector(s), 127); }
  void init(const vector<int> &v, int maxnum = 0) {
    intv = v;
    intv.push_back(-1);
    sa.resize(intv.size());
    arr = sa.begin();
    sa_is(intv.begin(), intv.size(), (maxnum ? maxnum : *max_element(intv.begin(), intv.end())) + 1);
    init_lcp(intv);
  }
  int lower_bound(const string &s) const { return lower_bound(string_to_vector(s)); }
  int lower_bound(const vector<int> &v) const {
    int l = 0, r = intv.size(), m = (l + r) / 2, h1, h2;
    pair<int, int> comp = direct_compare(v, sa[m]);
    if (comp.first > 0) l = m, h1 = comp.second;
    else r = m, h1 = 0;
    while (r - l > 1) {
      m = (l + r) / 2, h2 = rmq.query(l, m);
      if (h1 < h2) l = m;
      else if (h1 > h2) r = m;
      else {
        comp = direct_compare(v, sa[m], h1);
        if (comp.first > 0) l = m, h1 = comp.second;
        else if (comp.first < 0) r = m;
        else { r = m; break; }
      }
    }
    return r;
  }
  int upper_bound(const string &s) const { vector<int> v = string_to_vector(s); return upper_bound(v); }
  int upper_bound(vector<int> &v) const {
    ++v.back();
    int upper = lower_bound(v);
    --v.back();
    return upper;
  }
  vector<int> search(const string &s) const { return search(s); }
  vector<int> search(vector<int> &v) const { return vector<int>(sa.begin() + lower_bound(v), sa.begin() + upper_bound(v)); }
  int operator[](int x) const { return sa[x]; }
  int size(void) const { return sa.size(); }
};

int main(void) {
  string t;
  int q;
  cin >> t >> q;
  vector<string> p(q);
  rep (i, q) cin >> p[i];
  SuffixArray sa(t);
  rep (i, q) cout << (sa.lower_bound(p[i]) != sa.upper_bound(p[i])) << "\n";
  return 0;
}

### Prompt

Your challenge is to write 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>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

class SuffixArray {
  template <typename T>
  class RangeMinmaxQuery {
    template <typename C>
    struct Compare { bool operator()(const C &a, const C &b) const { return a < b; } };
    template <typename S>
    class SparseTable {
      Compare<S> comp;
      vector<vector<int>> st;
      vector<int> lookup;
      vector<S>   origin;

      public:
      SparseTable(void) {}
      SparseTable(const vector<S> &v) { init(v); }
      void init(const vector<S> &v) {
        origin = v;
        int lg_size = 0, v_size = v.size();
        while ((1 << lg_size) <= v_size) ++lg_size;
        st.assign((1 << lg_size), vector<int>(lg_size));
        for (int i = 0; i < v_size; ++i) st[i][0] = i;
        for (int j = 1; j < lg_size; ++j) {
          for (int i = 0; i + (1 << j) <= (1 << lg_size); ++i) {
            int l = st[i][j - 1], r = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = comp(v[r], v[l]) ? r : l;
          }
        }
        lookup.assign(v_size + 1, 0);
        for (int i = 2; i <= v_size; ++i) lookup[i] = lookup[i >> 1] + 1;
      }
      S query(int l, int r) const {
        int lg_size = lookup[r - l];
        S   lret = origin[st[l][lg_size]], rret = origin[st[r - (1 << lg_size)][lg_size]];
        return comp(rret, lret) ? rret : lret;
      }
      int query_index(int l, int r) const {
        int lg_size = lookup[r - l];
        int lidx = st[l][lg_size], ridx = st[r - (1 << lg_size)][lg_size];
        return comp(origin[ridx], origin[lidx]) ? ridx : lidx;
      }
      int size(void) const { return st.size(); }
    };
    Compare<T> comp;
    int v_size, bl_size, bl_num;
    SparseTable<pair<T, int>> st;
    vector<int> bit;
    vector<T>   origin;
    static int lsb(const unsigned bit) {
      static constexpr int table[32] = {0,  1,  28, 2,  29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4,  8,
                                        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6,  11, 5,  10, 9};
      return table[((bit & -bit) * 0x077CB531) >> 27];
    }
    int block_query(const int l, const int r, const int bl_n) const {
      int bl_l = bl_size * bl_n, x = bit[r] & ~((1 << (l - bl_l)) - 1);
      return x ? bl_l + lsb(x) : r;
    }

    public:
    RangeMinmaxQuery(void) {}
    RangeMinmaxQuery(const vector<T> &v) { init(v); }
    void init(const vector<T> &v) {
      origin = v, v_size = v.size(), bl_size = 0;
      while ((1 << bl_size) < v_size) ++bl_size;
      bl_size = max(1, bl_size >> 1);
      bl_num  = (v_size + bl_size - 1) / bl_size;
      vector<pair<T, int>> bl_v(bl_num, {numeric_limits<T>::max(), INT_MAX});
      for (int i = 0, j = 0; i < v_size; ++i, j = i / bl_size) if (comp(v[i], bl_v[j].first)) bl_v[j] = {v[i], i};
      st.init(move(bl_v));
      bit.assign(v_size, 0);
      for (int i = 0, l = 0; i < bl_num; ++i, l += bl_size) {
        vector<int> helper(bl_size), inc(bl_size);
        for (int j = 0, now = -1, r = min(bl_size, v_size - l); j < r; ++j) {
          while (now >= 0 && !comp(v[l + inc[now]], v[l + j])) --now;
          helper[j]  = now >= 0 ? inc[now] : -1;
          inc[++now] = j;
        }
        for (int j = 0, r = min(bl_size, v_size - l); j < r; ++j) bit[l + j] = helper[j] >= 0 ? bit[l + helper[j]] | (1 << helper[j]) : 0;
      }
    }
    T   query(const int l, const int r) const { return origin[query_index(l, r)]; }
    int query_index(int l, int r) const {
      int lbl_n = l / bl_size, rbl_n = --r / bl_size, lbl_p = l % bl_size, rbl_p = r % bl_size;
      if (lbl_n == rbl_n) return block_query(l, r, lbl_n);
      int lret = lbl_p > 0 ? block_query(l, l - lbl_p + bl_size - 1, lbl_n++) : l;
      int rlet = rbl_p < bl_size - 1 ? block_query(r - rbl_p, r, rbl_n--) : r;
      int ret  = comp(origin[rlet], origin[lret]) ? rlet : lret;
      if (lbl_n <= rbl_n) {
        pair<T, int> mret = st.query(lbl_n, rbl_n + 1);
        if (comp(mret.first, origin[ret])) ret = mret.second;
      }
      return ret;
    }
    int size(void) const { return v_size; }
  };
  vector<int>::iterator arr;
  vector<int> string_to_vector(const string &s) const { return vector<int>(s.begin(), s.end()); }
  bool lms(const int i, const vector<bool> &ltype) const { return i > 0 && !ltype[i] && ltype[i - 1]; }
  vector<int> get_count(const vector<int>::const_iterator &str, const int len, const int chnum) const {
    vector<int> cnt(chnum + 1);
    for (int i = 0; i < len; ++i) ++cnt[str[i]];
    return cnt;
  }
  vector<int> get_buckets(const vector<int> &cnt, const bool back) const {
    int clen = cnt.size(), sum = 1;
    vector<int> buckets(clen);
    for (int i = 0; i < clen; ++i) {
      sum += cnt[i];
      buckets[i] = back ? sum : sum - cnt[i];
    }
    return buckets;
  }
  void induced_sort_ls(const vector<int>::const_iterator &str, const int len, const vector<bool> &ltype, const vector<int> &cnt, vector<int> &buckets) {
    int prev;
    buckets = get_buckets(cnt, false);
    for (int i = 0; i < len; ++i) {
      if ((prev = arr[i] - 1) >= 0 && ltype[prev]) arr[buckets[str[prev]]++] = prev;
    }
    buckets = get_buckets(cnt, true);
    for (int i = len - 1; i >= 0; --i) {
      if ((prev = arr[i] - 1) >= 0 && !ltype[prev]) arr[--buckets[str[prev]]] = prev;
    }
  }
  void sa_is(const vector<int>::const_iterator &str, int len, const int chmax) {
    fill(arr, arr + len, -1);
    vector<bool> ltype(len);
    ltype[len - 2] = true;
    for (int i = len - 3; i >= 0; --i) ltype[i] = str[i] > str[i + 1] || (str[i] == str[i + 1] && ltype[i + 1] == true);
    vector<int> cnt = get_count(str, len - 1, chmax), buckets = get_buckets(cnt, true);
    arr[0] = len - 1;
    for (int i = 1; i < len - 1; ++i) if (lms(i, ltype)) arr[--buckets[str[i]]] = i;
    induced_sort_ls(str, len, ltype, cnt, buckets);
    int lms_num = 0, now = -1, prev = -1, name = -1, mid = len / 2;
    for (int i = 0; i < len; ++i) if (lms(arr[i], ltype)) arr[lms_num++] = arr[i];
    fill(arr + lms_num, arr + len, -1);
    for (int i = 0; i < lms_num; ++i) {
      prev = now; now  = arr[i];
      for (int nowp = now, prevp = prev; nowp < len && prevp < len; ++nowp, ++prevp) {
        int lmscheck = (lms(nowp, ltype)) + lms(prevp, ltype);
        if (prev == -1 || str[nowp] != str[prevp] || lmscheck & 1) { ++name; break; }
        if (lmscheck && nowp > now) break;
      }
      arr[lms_num + now / 2] = name;
    }
    for (int i = len - 1, j = i; i >= lms_num; --i) if (arr[i] >= 0) arr[j--] = arr[i];
    vector<int>::iterator arr2 = arr + len - lms_num;
    if (lms_num == name + 1) {
      for (int i = 0; i < lms_num; ++i) arr[arr2[i]] = i;
    } else {
      sa_is(arr2, lms_num, name);
    }
    for (int i = 0, j = 0; i < len; ++i) if (lms(i, ltype)) arr2[j++] = i;
    for (int i = 0; i < lms_num; ++i) arr[i] = arr2[arr[i]];
    fill(arr + lms_num, arr + len, -1);
    buckets = get_buckets(cnt, true);
    for (int i = lms_num - 1; i > 0; --i) {
      int x = arr[i];
      arr[i] = -1;
      arr[--buckets[str[x]]] = x;
    }
    induced_sort_ls(str, len, ltype, cnt, buckets);
  }
  void init_lcp(const vector<int> &v) {
    const int len = sa.size() - 1;
    lcp.assign(len + 1, 0);
    lcp[len] = len;
    vector<int> rank(len + 1);
    for (int i = 0; i <= len; ++i) rank[sa[i]] = i;
    int h = 0;
    for (int now = 0; now < len; ++now) {
      int prev = sa[rank[now] - 1];
      if (h > 0) --h;
      for (; now + h < len && prev + h < len && v[now + h] == v[prev + h]; ++h);
      lcp[rank[now] - 1] = h;
    }
    rmq.init(lcp);
  }
  pair<int, int> direct_compare(const vector<int> &v, int pos, int h = 0) const {
    int olen = intv.size() - pos - 1, vlen = v.size(), comp;
    pos += h;
    for (int r = min(olen, vlen); h < r && intv[pos] == v[h]; ++h, ++pos);
    if (h == vlen) comp = -1;
    else if (h == olen) comp = 1;
    else comp = (intv[pos] < v[h]) - (intv[pos] > v[h]);
    return {comp, h};
  }
  RangeMinmaxQuery<int> rmq;

  public:
  vector<int> sa, lcp, intv;

  SuffixArray(void) {}
  SuffixArray(const string &s) { init(s); }
  SuffixArray(vector<int> &v) { init(v); }
  void init(const string &s) { init(string_to_vector(s), 127); }
  void init(const vector<int> &v, int maxnum = 0) {
    intv = v;
    intv.push_back(-1);
    sa.resize(intv.size());
    arr = sa.begin();
    sa_is(intv.begin(), intv.size(), (maxnum ? maxnum : *max_element(intv.begin(), intv.end())) + 1);
    init_lcp(intv);
  }
  int lower_bound(const string &s) const { return lower_bound(string_to_vector(s)); }
  int lower_bound(const vector<int> &v) const {
    int l = 0, r = intv.size(), m = (l + r) / 2, h1, h2;
    pair<int, int> comp = direct_compare(v, sa[m]);
    if (comp.first > 0) l = m, h1 = comp.second;
    else r = m, h1 = 0;
    while (r - l > 1) {
      m = (l + r) / 2, h2 = rmq.query(l, m);
      if (h1 < h2) l = m;
      else if (h1 > h2) r = m;
      else {
        comp = direct_compare(v, sa[m], h1);
        if (comp.first > 0) l = m, h1 = comp.second;
        else if (comp.first < 0) r = m;
        else { r = m; break; }
      }
    }
    return r;
  }
  int upper_bound(const string &s) const { vector<int> v = string_to_vector(s); return upper_bound(v); }
  int upper_bound(vector<int> &v) const {
    ++v.back();
    int upper = lower_bound(v);
    --v.back();
    return upper;
  }
  vector<int> search(const string &s) const { return search(s); }
  vector<int> search(vector<int> &v) const { return vector<int>(sa.begin() + lower_bound(v), sa.begin() + upper_bound(v)); }
  int operator[](int x) const { return sa[x]; }
  int size(void) const { return sa.size(); }
};

int main(void) {
  string t;
  int q;
  cin >> t >> q;
  vector<string> p(q);
  rep (i, q) cin >> p[i];
  SuffixArray sa(t);
  rep (i, q) cout << (sa.lower_bound(p[i]) != sa.upper_bound(p[i])) << "\n";
  return 0;
}

```