#include<iostream>
#include<algorithm>
using namespace std;

int n, k;
int rnk[1000001];
int tmp[1000001];

bool compare_sa(int i, int j){
    if(rnk[i] != rnk[j]){
        return rnk[i] < rnk[j];
    }else{
        int ri = i+k <= n ? rnk[i+k] : -1;
        int rj = j+k <= n ? rnk[j+k] : -1;
        return ri < rj;
    }
}

void construct_sa(string s, int *sa){
    n = s.length();
    for(int i = 0; i <= n; i++){
        sa[i] = i;
        rnk[i] = i < n ? s[i] : -1;
    }
    for(k = 1; k <= n; k *= 2){
        sort(sa, sa+n+1, compare_sa);
        tmp[sa[0]] = 0;
        for(int i = 1; i <= n; i++){
            tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
        }
        for(int i = 0; i <= n; i++){
            rnk[i] = tmp[i];
        }
    }
}

bool contain(string s, int *sa, string t){
    int a = 0, b = s.length();
    while(b - a > 1){
        int c = (a+b)/2;
        if(s.compare(sa[c], t.length(), t) < 0) a = c;
        else    b = c;
    }
    return s.compare(sa[b], t.length(), t) == 0;
}

int main(){
    string s;
    cin >> s;
    n = s.length();
    int sa[n];
    construct_sa(s, sa);
    int q;
    cin >> q;
    while(q-- > 0){
        string t;
        cin >> t;
        cout << contain(s, sa, t) << endl;
    }
    return 0;
}

### Prompt

Generate 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<iostream>
#include<algorithm>
using namespace std;

int n, k;
int rnk[1000001];
int tmp[1000001];

bool compare_sa(int i, int j){
    if(rnk[i] != rnk[j]){
        return rnk[i] < rnk[j];
    }else{
        int ri = i+k <= n ? rnk[i+k] : -1;
        int rj = j+k <= n ? rnk[j+k] : -1;
        return ri < rj;
    }
}

void construct_sa(string s, int *sa){
    n = s.length();
    for(int i = 0; i <= n; i++){
        sa[i] = i;
        rnk[i] = i < n ? s[i] : -1;
    }
    for(k = 1; k <= n; k *= 2){
        sort(sa, sa+n+1, compare_sa);
        tmp[sa[0]] = 0;
        for(int i = 1; i <= n; i++){
            tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
        }
        for(int i = 0; i <= n; i++){
            rnk[i] = tmp[i];
        }
    }
}

bool contain(string s, int *sa, string t){
    int a = 0, b = s.length();
    while(b - a > 1){
        int c = (a+b)/2;
        if(s.compare(sa[c], t.length(), t) < 0) a = c;
        else    b = c;
    }
    return s.compare(sa[b], t.length(), t) == 0;
}

int main(){
    string s;
    cin >> s;
    n = s.length();
    int sa[n];
    construct_sa(s, sa);
    int q;
    cin >> q;
    while(q-- > 0){
        string t;
        cin >> t;
        cout << contain(s, sa, t) << endl;
    }
    return 0;
}

```