#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
 
#define MAX 1000002
 
typedef unsigned char byte;
byte mask[8] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
  
int *Lv;
int n, k;
  
bool cmp_Lv(const int i, const int j){ return Lv[i] < Lv[j]; }
  
bool cmp(const int i, const int j){
    if(Lv[i] != Lv[j]){ return Lv[i] < Lv[j]; }
    int L_i = (i + k >= n ? -1 : Lv[i + k]);
    int L_j = (j + k >= n ? -1 : Lv[j + k]);
  
    return L_i < L_j;
}
  
int main()
{
    int *A;
    char c[MAX];
    scanf("%s", c);
    std::string T = std::string(c);
    n = T.size();
 
    A = new int[n + 1], Lv = new int [n + 1];
 
    byte *t;
    t = new byte [(n >> 3) + 1];
  
    int i;
    for(i = 0; i < n; i++){ A[i] = i; }
    for(i = 0; i < n; i++){ Lv[i] = T[i]; }
  
    int bkt[129];
    for(i = 0; i < 129; i++){ bkt[i] = 0; }
    for(i = 0; i < n; i++){ bkt[Lv[i]]++; }
    int sum = 0;
    for(i = 0; i < 129; i++){ sum += bkt[i]; bkt[i] = sum; }
    for(i = 0; i < n; i++){ A[--bkt[Lv[i]]] = i; }
  
    for(i = 1; i < n; i++){
        t[i >> 3] = (Lv[A[i]] != Lv[A[i - 1]] ? t[i >> 3] | mask[i & 7] : t[i >> 3] & ~mask[i & 7]);
    }
    t[n >> 3] = t[n >> 3] | mask[n & 7];
  
    Lv[A[0]] = 0;
    for(i = 1; i < n; i++){
        Lv[A[i]] = Lv[A[i - 1]] + !!(mask[i & 7] & t[i >> 3]);
    }
  
    k = 1;
    while(1){
        if(k > n) break;
 
        std::sort(A, A + n, cmp);
  
        for(i = 1; i < n; i++){
            t[i >> 3] = (cmp(A[i - 1], A[i]) ? t[i >> 3] | mask[i & 7] : t[i >> 3] & ~mask[i & 7]);
        }
        Lv[A[0]] = 0;
        for(i = 1; i < n; i++){
            Lv[A[i]] = Lv[A[i - 1]] + !!(mask[i & 7] & t[i >> 3]);
        }
 
        if(Lv[A[n - 1]] == n - 1) break;
        k <<= 1;
    };
  
    char p[1000];
    int q, left, right, mid, crit;
    bool exist;
    scanf("%d", &q);
  
    A[n] = n;
  
    while(q){
        scanf("%s", p);
        std::string P = std::string(p);
        left = 0, right = n, exist = false;
        while(left < right){
  
            if(n < P.size()){ exist = false; break; }
  
            mid = (left + right) / 2;
            crit = T.compare(A[mid], P.size(), P);
  
            if(crit > 0){ right = mid; }
            else if(crit < 0){ left = mid + 1; }
            else{ exist = true; break; }
        };
        if(T.compare(A[right], P.size(), P) == 0) exist = true;
        if(exist){ printf("1\n"); }else{ printf("0\n"); }
        q--;
    }
    return 0;
}
### 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<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
 
#define MAX 1000002
 
typedef unsigned char byte;
byte mask[8] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
  
int *Lv;
int n, k;
  
bool cmp_Lv(const int i, const int j){ return Lv[i] < Lv[j]; }
  
bool cmp(const int i, const int j){
    if(Lv[i] != Lv[j]){ return Lv[i] < Lv[j]; }
    int L_i = (i + k >= n ? -1 : Lv[i + k]);
    int L_j = (j + k >= n ? -1 : Lv[j + k]);
  
    return L_i < L_j;
}
  
int main()
{
    int *A;
    char c[MAX];
    scanf("%s", c);
    std::string T = std::string(c);
    n = T.size();
 
    A = new int[n + 1], Lv = new int [n + 1];
 
    byte *t;
    t = new byte [(n >> 3) + 1];
  
    int i;
    for(i = 0; i < n; i++){ A[i] = i; }
    for(i = 0; i < n; i++){ Lv[i] = T[i]; }
  
    int bkt[129];
    for(i = 0; i < 129; i++){ bkt[i] = 0; }
    for(i = 0; i < n; i++){ bkt[Lv[i]]++; }
    int sum = 0;
    for(i = 0; i < 129; i++){ sum += bkt[i]; bkt[i] = sum; }
    for(i = 0; i < n; i++){ A[--bkt[Lv[i]]] = i; }
  
    for(i = 1; i < n; i++){
        t[i >> 3] = (Lv[A[i]] != Lv[A[i - 1]] ? t[i >> 3] | mask[i & 7] : t[i >> 3] & ~mask[i & 7]);
    }
    t[n >> 3] = t[n >> 3] | mask[n & 7];
  
    Lv[A[0]] = 0;
    for(i = 1; i < n; i++){
        Lv[A[i]] = Lv[A[i - 1]] + !!(mask[i & 7] & t[i >> 3]);
    }
  
    k = 1;
    while(1){
        if(k > n) break;
 
        std::sort(A, A + n, cmp);
  
        for(i = 1; i < n; i++){
            t[i >> 3] = (cmp(A[i - 1], A[i]) ? t[i >> 3] | mask[i & 7] : t[i >> 3] & ~mask[i & 7]);
        }
        Lv[A[0]] = 0;
        for(i = 1; i < n; i++){
            Lv[A[i]] = Lv[A[i - 1]] + !!(mask[i & 7] & t[i >> 3]);
        }
 
        if(Lv[A[n - 1]] == n - 1) break;
        k <<= 1;
    };
  
    char p[1000];
    int q, left, right, mid, crit;
    bool exist;
    scanf("%d", &q);
  
    A[n] = n;
  
    while(q){
        scanf("%s", p);
        std::string P = std::string(p);
        left = 0, right = n, exist = false;
        while(left < right){
  
            if(n < P.size()){ exist = false; break; }
  
            mid = (left + right) / 2;
            crit = T.compare(A[mid], P.size(), P);
  
            if(crit > 0){ right = mid; }
            else if(crit < 0){ left = mid + 1; }
            else{ exist = true; break; }
        };
        if(T.compare(A[right], P.size(), P) == 0) exist = true;
        if(exist){ printf("1\n"); }else{ printf("0\n"); }
        q--;
    }
    return 0;
}
```