#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}
class SuffixArray {
    const ll n;
    const string str;
    vector<ll> sa, lcp;
public:
    SuffixArray(const string& s) : str(s), n(s.size()) {}
    vector<ll> make_sa() {
        sa.assign(n+1, 0);
        rep(i, n+1) sa[i] = i;
        vector<ll> rank(all(str));
        rank.pb(-1);
        auto f = [&](ll idx, ll len) {
            return idx + len <= n ? rank[idx+len] : -1;
        };
        for (ll k = 1; k <= n; k <<= 1) {
            auto compare = [&](ll a, ll b) {
                if (rank[a] != rank[b]) return rank[a] < rank[b];
                else return f(a, k) < f(b, k);
            };
            sort(all(sa), compare);
            vector<ll> nrank(n+1, 0);
            rep(i, 1, n+1) {
                nrank[sa[i]] = nrank[sa[i-1]] + compare(sa[i-1], sa[i]);
            }
            rank = nrank;
        }
        return sa;
    }
    vector<ll> make_lcp() {
        assert(sa.size() > 0);
        lcp.assign(sa.size(), 0);
        vector<ll> rank(n+1);
        rep(i, n+1) rank[sa[i]] = i;
        ll h = 0;
        rep(i, n) {
            if (h > 0) --h;
            assert(rank[i] > 0);
            for (ll j = sa[rank[i]-1]; j + h < n && i + h < n; h++) {
                if (str[j+h] != str[i+h]) break;
            }
            lcp[rank[i]-1] = h;
        }
        return lcp;
    }
    vector<ll> search(const string& s) {
        assert(lcp.size() > 0);
        ll l = -1, r = -1;
        {
            ll lb = 0, ub = n+1;
            while (ub - lb > 1) {
                ll mid = (lb + ub) / 2;
                if (str.substr(sa[mid], s.size()) >= s) {
                    ub = mid;
                }
                else {
                    lb = mid;
                }
            }
            l = ub;
        }
        {
            ll lb = 0, ub = n+1;
            while (ub - lb > 1) {
                ll mid = (lb + ub) / 2;
                if (str.substr(sa[mid], s.size()) > s) {
                    ub = mid;
                }
                else {
                    lb = mid;
                }
            }
            r = ub;
        }
        vector<ll> res;
        if (str.substr(sa[l], s.size()) == s) {
            rep(i, l, r) {
                res.pb(sa[i]);
            }
        }
        return res;
    }
};
// s[mid...] > t ?
ll compare(const string& s, const ll base, const string& t) {
    rep(i, t.size()) {
        if (base + i >= s.size()) return -1;
        if (s[base + i] != t[i]) return s[base+i] > t[i] ? 1 : -1;
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string S; cin >> S;
    SuffixArray Sa(S);
    vector<ll> sa = Sa.make_sa();
    ll Q; cin >> Q;
    rep(q, Q) {
        string s; cin >> s;
        ll lb = 0, ub = S.size();
        bool flag = true;
        while (flag) {
            ll mid = (ub + lb) / 2;
            // if (S.substr(sa[mid]) >= s) {
            if ( compare(S, sa[mid], s) >= 0 ) {
                ub = mid;
            }
            else {
                lb = mid;
            }
            if (ub - lb <= 1) flag = false;
        }
        // if (S.substr(sa[ub], s.size()) == s) cout << 1 << endl;
        if (compare(S, sa[ub], s) == 0) cout << 1 << endl;
        else cout << 0 << endl;
    }
}
### Prompt

Construct a cpp code solution to the problem outlined:

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 pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}
class SuffixArray {
    const ll n;
    const string str;
    vector<ll> sa, lcp;
public:
    SuffixArray(const string& s) : str(s), n(s.size()) {}
    vector<ll> make_sa() {
        sa.assign(n+1, 0);
        rep(i, n+1) sa[i] = i;
        vector<ll> rank(all(str));
        rank.pb(-1);
        auto f = [&](ll idx, ll len) {
            return idx + len <= n ? rank[idx+len] : -1;
        };
        for (ll k = 1; k <= n; k <<= 1) {
            auto compare = [&](ll a, ll b) {
                if (rank[a] != rank[b]) return rank[a] < rank[b];
                else return f(a, k) < f(b, k);
            };
            sort(all(sa), compare);
            vector<ll> nrank(n+1, 0);
            rep(i, 1, n+1) {
                nrank[sa[i]] = nrank[sa[i-1]] + compare(sa[i-1], sa[i]);
            }
            rank = nrank;
        }
        return sa;
    }
    vector<ll> make_lcp() {
        assert(sa.size() > 0);
        lcp.assign(sa.size(), 0);
        vector<ll> rank(n+1);
        rep(i, n+1) rank[sa[i]] = i;
        ll h = 0;
        rep(i, n) {
            if (h > 0) --h;
            assert(rank[i] > 0);
            for (ll j = sa[rank[i]-1]; j + h < n && i + h < n; h++) {
                if (str[j+h] != str[i+h]) break;
            }
            lcp[rank[i]-1] = h;
        }
        return lcp;
    }
    vector<ll> search(const string& s) {
        assert(lcp.size() > 0);
        ll l = -1, r = -1;
        {
            ll lb = 0, ub = n+1;
            while (ub - lb > 1) {
                ll mid = (lb + ub) / 2;
                if (str.substr(sa[mid], s.size()) >= s) {
                    ub = mid;
                }
                else {
                    lb = mid;
                }
            }
            l = ub;
        }
        {
            ll lb = 0, ub = n+1;
            while (ub - lb > 1) {
                ll mid = (lb + ub) / 2;
                if (str.substr(sa[mid], s.size()) > s) {
                    ub = mid;
                }
                else {
                    lb = mid;
                }
            }
            r = ub;
        }
        vector<ll> res;
        if (str.substr(sa[l], s.size()) == s) {
            rep(i, l, r) {
                res.pb(sa[i]);
            }
        }
        return res;
    }
};
// s[mid...] > t ?
ll compare(const string& s, const ll base, const string& t) {
    rep(i, t.size()) {
        if (base + i >= s.size()) return -1;
        if (s[base + i] != t[i]) return s[base+i] > t[i] ? 1 : -1;
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string S; cin >> S;
    SuffixArray Sa(S);
    vector<ll> sa = Sa.make_sa();
    ll Q; cin >> Q;
    rep(q, Q) {
        string s; cin >> s;
        ll lb = 0, ub = S.size();
        bool flag = true;
        while (flag) {
            ll mid = (ub + lb) / 2;
            // if (S.substr(sa[mid]) >= s) {
            if ( compare(S, sa[mid], s) >= 0 ) {
                ub = mid;
            }
            else {
                lb = mid;
            }
            if (ub - lb <= 1) flag = false;
        }
        // if (S.substr(sa[ub], s.size()) == s) cout << 1 << endl;
        if (compare(S, sa[ub], s) == 0) cout << 1 << endl;
        else cout << 0 << endl;
    }
}
```