#include <cassert>
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

#define isLMS(i) (i > 0 && t[i] && !t[i - 1])

// find the start or end of each bucket
template <typename T> void getBuckets(T* s, int* bkt, int n, int K, bool end) {
    int sum = 0;
    for (int i = 0; i <= K; i++)
        bkt[i] = 0; // clear all buckets
    for (int i = 0; i < n; i++)
        bkt[s[i]]++; // compute the size of each bucket
    for (int i = 0; i <= K; i++) {
        sum += bkt[i];
        bkt[i] = end ? sum : sum - bkt[i];
    }
}

// compute SAl
template <typename T>
void induceSAl(std::vector<bool>& t, int* SA, T* s, int* bkt, int n, int K) {
    getBuckets(s, bkt, n, K, false); // find starts of buckets
    for (int i = 0; i < n; i++) {
        int j = SA[i] - 1;
        if (j >= 0 && !t[j])
            SA[bkt[s[j]]++] = j;
    }
}

// compute SAs
template <typename T>
void induceSAs(std::vector<bool>& t, int* SA, T* s, int* bkt, int n, int K) {
    getBuckets(s, bkt, n, K, true); // find ends of buckets
    for (int i = n - 1; i >= 0; i--) {
        int j = SA[i] - 1;
        if (j >= 0 && t[j])
            SA[--bkt[s[j]]] = j;
    }
}

// find the suffix array SA of s[0..n-1] in {1..K}^n
// require s[n-1]=0 (the sentinel!), n>=2
// use a working space (excluding s and SA) of at most 2.25n+O(1) for a constant
// alphabet
template <typename T> void SA_IS(T* s, int* SA, int n, int K) {

    std::vector<bool> t(n);

    // Classify the type of each character
    t[n - 2] = 0;
    t[n - 1] = 1; // the sentinel must be in s1, important!!!
    for (int i = n - 3; i >= 0; i--)
        t[i] = (s[i] < s[i + 1] || (s[i] == s[i + 1] && t[i + 1] == 1)) ? 1 : 0;

    // stage 1: reduce the problem by at least 1/2
    // sort all the S-substrings
    int* bkt = (int*)malloc(sizeof(int) * (K + 1)); // bucket array
    getBuckets(s, bkt, n, K, true);                  // find ends of buckets
    for (int i = 0; i < n; i++)
        SA[i] = -1;
    for (int i = 1; i < n; i++)
        if (isLMS(i))
            SA[--bkt[s[i]]] = i;

    induceSAl(t, SA, s, bkt, n, K);
    induceSAs(t, SA, s, bkt, n, K);
    free(bkt);

    // compact all the sorted substrings into the first n1 items of SA
    // 2*n1 must be not larger than n (proveable)
    int n1 = 0;
    for (int i = 0; i < n; i++)
        if (isLMS(SA[i]))
            SA[n1++] = SA[i];

    // find the lexicographic names of all substrings
    for (int i = n1; i < n; i++)
        SA[i] = -1; // init the name array buffer
    int name = 0, prev = -1;
    for (int i = 0; i < n1; i++) {
        int pos = SA[i];
        bool diff = false;
        for (int d = 0; d < n; d++)
            if (prev == -1 || s[pos + d] != s[prev + d] ||
                t[pos + d] != t[prev + d]) {
                diff = true;
                break;
            }
            else if (d > 0 && (isLMS(pos + d) || isLMS(prev + d)))
                break;
        if (diff) {
            name++;
            prev = pos;
        }
        pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
        SA[n1 + pos] = name - 1;
    }
    for (int i = n - 1, j = n - 1; i >= n1; i--)
        if (SA[i] >= 0)
            SA[j--] = SA[i];

    // stage 2: solve the reduced problem
    // recurse if names are not yet unique
    int* SA1 = SA, * s1 = SA + n - n1;
    if (name < n1)
        SA_IS(s1, SA1, n1, name - 1);
    else // generate the suffix array of s1 directly
        for (int i = 0; i < n1; i++)
            SA1[s1[i]] = i;

    // stage 3: induce the result for the original problem
    bkt = (int*)malloc(sizeof(int) * (K + 1)); // bucket array
    // put all left-most S characters into their buckets
    getBuckets(s, bkt, n, K, true); // find ends of buckets
    for (int i = 1, j = 0; i < n; i++)
        if (isLMS(i))
            s1[j++] = i; // get p1
    for (int i = 0; i < n1; i++)
        SA1[i] = s1[SA1[i]]; // get index in s
    for (int i = n1; i < n; i++)
        SA[i] = -1; // init SA[n1..n-1]
    for (int i = n1 - 1; i >= 0; i--) {
        int j = SA[i];
        SA[i] = -1;
        SA[--bkt[s[j]]] = j;
    }
    induceSAl(t, SA, s, bkt, n, K);
    induceSAs(t, SA, s, bkt, n, K);
    free(bkt);
    //free(t);
}


bool starts_with(const char* target, const char* pattern) {
    for (;;) {
        if (*target != *pattern) return false;
        ++target;
        ++pattern;
        if (!*pattern) return true;
    }
}

int compare(const char* target, const char* pattern) {
    for (;;) {
        if (*target != *pattern) {
            if (*target > * pattern) return 1;
            else return -1;
        }
        ++target;
        ++pattern;
        if (!*pattern) return 0;
    }
}

bool search(string t, int* SA, int n, string p) {
    int lower = 0;              // 探索範囲の下限の添字
    int upper = n - 1;  // 探索範囲の上限の添字


    const char* target = t.c_str();
    const char* pattern = p.c_str();
    while (lower <= upper) {  // 上限と下限が逆転したら終わり

        // 中央の位置を求める
        int mid = (lower + upper) / 2;

        int n = SA[mid];
        
        int ret = compare(target + n, pattern);
        if (ret == 0) {
            return true;
        }
        if (ret < 0) {
            lower = mid + 1;  // 次は中央より後ろを調べるため、下限を変更
        }
        else {
            upper = mid - 1;  // 次は中央より手前を調べるため、上限を変更
        }
    }

    return false;
}

int SA[1000002];
int main() {
#if 0
    unsigned char s[100] = "mmiissiissiippii";
    SA_IS(s, SA, 17, 128);
    assert(SA[0] == 16);
    assert(SA[1] == 15);
    assert(SA[2] == 14);
    assert(SA[3] == 10);
    assert(SA[4] == 6);
    assert(SA[5] == 2);
    assert(SA[6] == 11);
    assert(SA[7] == 7);
    assert(SA[8] == 3);
    assert(SA[9] == 1);
    assert(SA[10] == 0);
    assert(SA[11] == 13);
    assert(SA[12] == 12);
    assert(SA[13] == 9);
    assert(SA[14] == 5);
    assert(SA[15] == 8);
    assert(SA[16] == 4);

    // #=> [16, 15, 14, 10, 6, 2, 11, 7, 3, 1, 0, 13, 12, 9, 5, 8, 4]

    assert(starts_with("mmiissiissiippii", "mmiissiissiippii"));
    assert(starts_with("mmiissiissiippii", "mmiissiissi"));
    assert(!starts_with("miissiissiippii", "mmiissiissi"));
#endif
#if 0
    pair<string, vector<ptrdiff_t>> sara_string_test_data[] = {
      { "mmiissiissiippii",
        { 15, 14, 10, 6, 2, 11, 7, 3, 1, 0, 13, 12, 9, 5, 8, 4 } },
      { "mmiissiippiissii",
        { 15, 14, 6, 10, 2, 7, 11, 3, 1, 0, 9, 8, 13, 5, 12, 4 } },
      { "abracadabra", { 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2 } },
      { "aeadacab", { 6, 4, 2, 0, 7, 5, 3, 1 } },
      { "abracadabra0AbRa4Cad14abra",
        { 11, 20, 16, 21, 12, 17, 14, 25, 10, 15, 22, 7, 0, 3, 18, 5, 13, 23, 8, 1,
          4, 19, 6, 24, 9, 2} }
    };
#endif

#if 1
    string t;
    cin >> t;

    SA_IS((unsigned char*)t.c_str(), SA, t.size() + 1, 128);

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        string x;
        cin >> x;
        cout << search(t, SA, t.size() + 1, x) << endl;
    }
#endif
    //std::cout << "Hello World!\n";
    return 0;
}


### Prompt

Please formulate 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 <cassert>
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

#define isLMS(i) (i > 0 && t[i] && !t[i - 1])

// find the start or end of each bucket
template <typename T> void getBuckets(T* s, int* bkt, int n, int K, bool end) {
    int sum = 0;
    for (int i = 0; i <= K; i++)
        bkt[i] = 0; // clear all buckets
    for (int i = 0; i < n; i++)
        bkt[s[i]]++; // compute the size of each bucket
    for (int i = 0; i <= K; i++) {
        sum += bkt[i];
        bkt[i] = end ? sum : sum - bkt[i];
    }
}

// compute SAl
template <typename T>
void induceSAl(std::vector<bool>& t, int* SA, T* s, int* bkt, int n, int K) {
    getBuckets(s, bkt, n, K, false); // find starts of buckets
    for (int i = 0; i < n; i++) {
        int j = SA[i] - 1;
        if (j >= 0 && !t[j])
            SA[bkt[s[j]]++] = j;
    }
}

// compute SAs
template <typename T>
void induceSAs(std::vector<bool>& t, int* SA, T* s, int* bkt, int n, int K) {
    getBuckets(s, bkt, n, K, true); // find ends of buckets
    for (int i = n - 1; i >= 0; i--) {
        int j = SA[i] - 1;
        if (j >= 0 && t[j])
            SA[--bkt[s[j]]] = j;
    }
}

// find the suffix array SA of s[0..n-1] in {1..K}^n
// require s[n-1]=0 (the sentinel!), n>=2
// use a working space (excluding s and SA) of at most 2.25n+O(1) for a constant
// alphabet
template <typename T> void SA_IS(T* s, int* SA, int n, int K) {

    std::vector<bool> t(n);

    // Classify the type of each character
    t[n - 2] = 0;
    t[n - 1] = 1; // the sentinel must be in s1, important!!!
    for (int i = n - 3; i >= 0; i--)
        t[i] = (s[i] < s[i + 1] || (s[i] == s[i + 1] && t[i + 1] == 1)) ? 1 : 0;

    // stage 1: reduce the problem by at least 1/2
    // sort all the S-substrings
    int* bkt = (int*)malloc(sizeof(int) * (K + 1)); // bucket array
    getBuckets(s, bkt, n, K, true);                  // find ends of buckets
    for (int i = 0; i < n; i++)
        SA[i] = -1;
    for (int i = 1; i < n; i++)
        if (isLMS(i))
            SA[--bkt[s[i]]] = i;

    induceSAl(t, SA, s, bkt, n, K);
    induceSAs(t, SA, s, bkt, n, K);
    free(bkt);

    // compact all the sorted substrings into the first n1 items of SA
    // 2*n1 must be not larger than n (proveable)
    int n1 = 0;
    for (int i = 0; i < n; i++)
        if (isLMS(SA[i]))
            SA[n1++] = SA[i];

    // find the lexicographic names of all substrings
    for (int i = n1; i < n; i++)
        SA[i] = -1; // init the name array buffer
    int name = 0, prev = -1;
    for (int i = 0; i < n1; i++) {
        int pos = SA[i];
        bool diff = false;
        for (int d = 0; d < n; d++)
            if (prev == -1 || s[pos + d] != s[prev + d] ||
                t[pos + d] != t[prev + d]) {
                diff = true;
                break;
            }
            else if (d > 0 && (isLMS(pos + d) || isLMS(prev + d)))
                break;
        if (diff) {
            name++;
            prev = pos;
        }
        pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
        SA[n1 + pos] = name - 1;
    }
    for (int i = n - 1, j = n - 1; i >= n1; i--)
        if (SA[i] >= 0)
            SA[j--] = SA[i];

    // stage 2: solve the reduced problem
    // recurse if names are not yet unique
    int* SA1 = SA, * s1 = SA + n - n1;
    if (name < n1)
        SA_IS(s1, SA1, n1, name - 1);
    else // generate the suffix array of s1 directly
        for (int i = 0; i < n1; i++)
            SA1[s1[i]] = i;

    // stage 3: induce the result for the original problem
    bkt = (int*)malloc(sizeof(int) * (K + 1)); // bucket array
    // put all left-most S characters into their buckets
    getBuckets(s, bkt, n, K, true); // find ends of buckets
    for (int i = 1, j = 0; i < n; i++)
        if (isLMS(i))
            s1[j++] = i; // get p1
    for (int i = 0; i < n1; i++)
        SA1[i] = s1[SA1[i]]; // get index in s
    for (int i = n1; i < n; i++)
        SA[i] = -1; // init SA[n1..n-1]
    for (int i = n1 - 1; i >= 0; i--) {
        int j = SA[i];
        SA[i] = -1;
        SA[--bkt[s[j]]] = j;
    }
    induceSAl(t, SA, s, bkt, n, K);
    induceSAs(t, SA, s, bkt, n, K);
    free(bkt);
    //free(t);
}


bool starts_with(const char* target, const char* pattern) {
    for (;;) {
        if (*target != *pattern) return false;
        ++target;
        ++pattern;
        if (!*pattern) return true;
    }
}

int compare(const char* target, const char* pattern) {
    for (;;) {
        if (*target != *pattern) {
            if (*target > * pattern) return 1;
            else return -1;
        }
        ++target;
        ++pattern;
        if (!*pattern) return 0;
    }
}

bool search(string t, int* SA, int n, string p) {
    int lower = 0;              // 探索範囲の下限の添字
    int upper = n - 1;  // 探索範囲の上限の添字


    const char* target = t.c_str();
    const char* pattern = p.c_str();
    while (lower <= upper) {  // 上限と下限が逆転したら終わり

        // 中央の位置を求める
        int mid = (lower + upper) / 2;

        int n = SA[mid];
        
        int ret = compare(target + n, pattern);
        if (ret == 0) {
            return true;
        }
        if (ret < 0) {
            lower = mid + 1;  // 次は中央より後ろを調べるため、下限を変更
        }
        else {
            upper = mid - 1;  // 次は中央より手前を調べるため、上限を変更
        }
    }

    return false;
}

int SA[1000002];
int main() {
#if 0
    unsigned char s[100] = "mmiissiissiippii";
    SA_IS(s, SA, 17, 128);
    assert(SA[0] == 16);
    assert(SA[1] == 15);
    assert(SA[2] == 14);
    assert(SA[3] == 10);
    assert(SA[4] == 6);
    assert(SA[5] == 2);
    assert(SA[6] == 11);
    assert(SA[7] == 7);
    assert(SA[8] == 3);
    assert(SA[9] == 1);
    assert(SA[10] == 0);
    assert(SA[11] == 13);
    assert(SA[12] == 12);
    assert(SA[13] == 9);
    assert(SA[14] == 5);
    assert(SA[15] == 8);
    assert(SA[16] == 4);

    // #=> [16, 15, 14, 10, 6, 2, 11, 7, 3, 1, 0, 13, 12, 9, 5, 8, 4]

    assert(starts_with("mmiissiissiippii", "mmiissiissiippii"));
    assert(starts_with("mmiissiissiippii", "mmiissiissi"));
    assert(!starts_with("miissiissiippii", "mmiissiissi"));
#endif
#if 0
    pair<string, vector<ptrdiff_t>> sara_string_test_data[] = {
      { "mmiissiissiippii",
        { 15, 14, 10, 6, 2, 11, 7, 3, 1, 0, 13, 12, 9, 5, 8, 4 } },
      { "mmiissiippiissii",
        { 15, 14, 6, 10, 2, 7, 11, 3, 1, 0, 9, 8, 13, 5, 12, 4 } },
      { "abracadabra", { 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2 } },
      { "aeadacab", { 6, 4, 2, 0, 7, 5, 3, 1 } },
      { "abracadabra0AbRa4Cad14abra",
        { 11, 20, 16, 21, 12, 17, 14, 25, 10, 15, 22, 7, 0, 3, 18, 5, 13, 23, 8, 1,
          4, 19, 6, 24, 9, 2} }
    };
#endif

#if 1
    string t;
    cin >> t;

    SA_IS((unsigned char*)t.c_str(), SA, t.size() + 1, 128);

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        string x;
        cin >> x;
        cout << search(t, SA, t.size() + 1, x) << endl;
    }
#endif
    //std::cout << "Hello World!\n";
    return 0;
}


```