#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

char str[1000001];
int k, len;
int sa[1000001], Rank[1000001], temp[1000001];

bool compare_sa(int i, int j) {
    if (Rank[i] == Rank[j]) {
        int t1 = -1, t2 = -1;
        if (i + k <= len) {
            t1 = Rank[i + k];
        }
        if (j + k <= len) {
            t2 = Rank[j + k];
        }
        return t1 < t2;
    }
    else {
        return Rank[i] < Rank[j];
    }
}

void construct_sa() {
    for (int i = 0; i <= len; i++) {
        sa[i] = i;
        if (i == len) {
            Rank[i] = -1;
        }
        else {
            Rank[i] = str[i];
        }
    }

    for (k = 1; k <= len; k *= 2) {
        sort(sa, sa + len + 1, compare_sa);
        
        temp[sa[0]] = 0;
        for (int i = 1; i <= len; i++) {
            temp[sa[i]] = temp[sa[i - 1]] + compare_sa(sa[i - 1], sa[i]);
        }
        for (int i = 0; i <= len; i++) {
            Rank[i] = temp[i];
        }
    }
}

int main() {
    cin >> str;
    len = strlen(str);

    construct_sa();

    int n, tlen;
    char t[1001];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t;
        tlen = strlen(t);
        int left = 0, right = len + 1, pivot;
        while (left + 1 < right) {
            pivot = (left + right) / 2;

            if (strncmp(str + sa[pivot], t, tlen) <= 0) {
                left = pivot;
            }
            else {
                right = pivot;
            }
        }
        cout << (strncmp(str + sa[left], t, tlen) == 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 <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

char str[1000001];
int k, len;
int sa[1000001], Rank[1000001], temp[1000001];

bool compare_sa(int i, int j) {
    if (Rank[i] == Rank[j]) {
        int t1 = -1, t2 = -1;
        if (i + k <= len) {
            t1 = Rank[i + k];
        }
        if (j + k <= len) {
            t2 = Rank[j + k];
        }
        return t1 < t2;
    }
    else {
        return Rank[i] < Rank[j];
    }
}

void construct_sa() {
    for (int i = 0; i <= len; i++) {
        sa[i] = i;
        if (i == len) {
            Rank[i] = -1;
        }
        else {
            Rank[i] = str[i];
        }
    }

    for (k = 1; k <= len; k *= 2) {
        sort(sa, sa + len + 1, compare_sa);
        
        temp[sa[0]] = 0;
        for (int i = 1; i <= len; i++) {
            temp[sa[i]] = temp[sa[i - 1]] + compare_sa(sa[i - 1], sa[i]);
        }
        for (int i = 0; i <= len; i++) {
            Rank[i] = temp[i];
        }
    }
}

int main() {
    cin >> str;
    len = strlen(str);

    construct_sa();

    int n, tlen;
    char t[1001];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t;
        tlen = strlen(t);
        int left = 0, right = len + 1, pivot;
        while (left + 1 < right) {
            pivot = (left + right) / 2;

            if (strncmp(str + sa[pivot], t, tlen) <= 0) {
                left = pivot;
            }
            else {
                right = pivot;
            }
        }
        cout << (strncmp(str + sa[left], t, tlen) == 0) << endl;
    }

    return 0;
}
```