#include <bits/stdc++.h>
using namespace std;

class SA{
public:
  string S;
  int n;
  vector<int> sa;
  
  SA():n(-1){}
  SA(string S):S(S),n(S.size()),sa(n){  
    vector<int> rnk(n);
    vector<int> tmp(n);
    for(int i=0;i<n;i++) sa[i]=i;
    for(int i=0;i<n;i++) rnk[i] = S[i];
    
    //k文字についてソートされているところから、2k文字でソート
    for(int Len=1;Len<=n;Len*=2){
      
      //(rnk[i],rnk[i+k])と(rnk[j],rnk[j+k])を比較
      auto compare_sa=[&](const int &i,const int &j){
        if(rnk[i]!=rnk[j])return rnk[i]<rnk[j];
        int ri=i+Len<n?rnk[i+Len]:-1;
        int rj=j+Len<n?rnk[j+Len]:-1;
        return ri<rj;
      };
      
      sort(sa.begin(),sa.end(),compare_sa);

      //いったんtmpに次のランクを計算して、rnkに代入
      for(int i=1;i<n;i++)
        tmp[sa[i]] = tmp[sa[i-1]] + compare_sa(sa[i-1],sa[i]);
      rnk = tmp;
    }
  }

  int lower_bound(string T){
    assert(n >= 0);
    int L=-1,R=S.length();
    while(L+1<R){
      int M = (L+R)/2;
      S.compare(sa[M],T.size(),T)<0? L = M:R = M;
    }
    return R;
  } 

  int upper_bound(string T){return lower_bound(T+char('z'+ 1));} 
  int count(string T){return upper_bound(T) - lower_bound(T);};
};

int main(){
  string s;
  cin>>s;
  SA sa(s);
  
  int q;
  cin>>q;
  while(q--){
    string t;
    cin>>t;
    int ans = sa.count(t) != 0;
    printf("%d\n",ans);
  }
  
}


### Prompt

Please create a solution in Cpp 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 <bits/stdc++.h>
using namespace std;

class SA{
public:
  string S;
  int n;
  vector<int> sa;
  
  SA():n(-1){}
  SA(string S):S(S),n(S.size()),sa(n){  
    vector<int> rnk(n);
    vector<int> tmp(n);
    for(int i=0;i<n;i++) sa[i]=i;
    for(int i=0;i<n;i++) rnk[i] = S[i];
    
    //k文字についてソートされているところから、2k文字でソート
    for(int Len=1;Len<=n;Len*=2){
      
      //(rnk[i],rnk[i+k])と(rnk[j],rnk[j+k])を比較
      auto compare_sa=[&](const int &i,const int &j){
        if(rnk[i]!=rnk[j])return rnk[i]<rnk[j];
        int ri=i+Len<n?rnk[i+Len]:-1;
        int rj=j+Len<n?rnk[j+Len]:-1;
        return ri<rj;
      };
      
      sort(sa.begin(),sa.end(),compare_sa);

      //いったんtmpに次のランクを計算して、rnkに代入
      for(int i=1;i<n;i++)
        tmp[sa[i]] = tmp[sa[i-1]] + compare_sa(sa[i-1],sa[i]);
      rnk = tmp;
    }
  }

  int lower_bound(string T){
    assert(n >= 0);
    int L=-1,R=S.length();
    while(L+1<R){
      int M = (L+R)/2;
      S.compare(sa[M],T.size(),T)<0? L = M:R = M;
    }
    return R;
  } 

  int upper_bound(string T){return lower_bound(T+char('z'+ 1));} 
  int count(string T){return upper_bound(T) - lower_bound(T);};
};

int main(){
  string s;
  cin>>s;
  SA sa(s);
  
  int q;
  cin>>q;
  while(q--){
    string t;
    cin>>t;
    int ans = sa.count(t) != 0;
    printf("%d\n",ans);
  }
  
}


```