#include<bits/stdc++.h>

#define rank Rank

using namespace std;

const int N=1e6+10;

int n,k;
int sa[N];
int rank[N];
int tmp[N];

string S,T;

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

void getSa()
{
    n=S.length();

    for(int i=0;i<=n;i++)
    {
        sa[i]=i;
        rank[i]=i<n?S[i]:-1;
    }

    for(k=1;k<=n;k<<=1)
    {
        sort(sa,sa+n+1,cmp);

        tmp[sa[0]]=0;
        for(int i=1;i<=n;i++)
        {
            tmp[sa[i]]=tmp[sa[i-1]]+(cmp(sa[i-1],sa[i])?1:0);
        }
        for(int i=0;i<=n;i++) rank[i]=tmp[i];
    }
}

bool contain()
{
    int l=0,r=S.length();
    while(r-l>1)
    {
        int mid=(l+r)>>1;
        if(S.compare(sa[mid],T.length(),T)<0) l=mid;
        else r=mid;
    }
    return S.compare(sa[r],T.length(),T)==0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>S;

    int number;

    cin>>number;

    getSa();

    while(number--)
    {
        cin>>T;
        cout<<contain()<<endl;
    }

    return 0;
}


### Prompt

Create a solution in CPP for 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>

#define rank Rank

using namespace std;

const int N=1e6+10;

int n,k;
int sa[N];
int rank[N];
int tmp[N];

string S,T;

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

void getSa()
{
    n=S.length();

    for(int i=0;i<=n;i++)
    {
        sa[i]=i;
        rank[i]=i<n?S[i]:-1;
    }

    for(k=1;k<=n;k<<=1)
    {
        sort(sa,sa+n+1,cmp);

        tmp[sa[0]]=0;
        for(int i=1;i<=n;i++)
        {
            tmp[sa[i]]=tmp[sa[i-1]]+(cmp(sa[i-1],sa[i])?1:0);
        }
        for(int i=0;i<=n;i++) rank[i]=tmp[i];
    }
}

bool contain()
{
    int l=0,r=S.length();
    while(r-l>1)
    {
        int mid=(l+r)>>1;
        if(S.compare(sa[mid],T.length(),T)<0) l=mid;
        else r=mid;
    }
    return S.compare(sa[r],T.length(),T)==0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>S;

    int number;

    cin>>number;

    getSa();

    while(number--)
    {
        cin>>T;
        cout<<contain()<<endl;
    }

    return 0;
}


```