#include <bits/stdc++.h>
#include <cmath>

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX / 10;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
typedef pair<int, int> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);


void print_line(vector<int> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;
const int mod = 1000000007;

void buildSA(const string &s, vector<ll> &sa, vector<ll> &rank) {
    int N = s.size();
    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<ll> &sa) {
    int a = 0, b = t.size(), m = p.size();
    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() {


    string text;
    cin >> text;
    vector<ll> sa, rank;
    buildSA(text, sa, rank);

    int l;
    cin >> l;
    rep(i, l) {
        string p;
        cin >> p;
        cout << (findSA(text, p, sa) != -1) << endl;
    }

}

### Prompt

Please create a solution in cpp 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>
#include <cmath>

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX / 10;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
typedef pair<int, int> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);


void print_line(vector<int> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;
const int mod = 1000000007;

void buildSA(const string &s, vector<ll> &sa, vector<ll> &rank) {
    int N = s.size();
    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<ll> &sa) {
    int a = 0, b = t.size(), m = p.size();
    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() {


    string text;
    cin >> text;
    vector<ll> sa, rank;
    buildSA(text, sa, rank);

    int l;
    cin >> l;
    rep(i, l) {
        string p;
        cin >> p;
        cout << (findSA(text, p, sa) != -1) << endl;
    }

}

```