////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// ?????¢
// XCode??§???EOF??\??????Ctrl+D
// ?\???Alt+\
// ans???????§?INT?????????2,147,483,647????¶????????????¨??????????????§long long?????£???????????????????????????
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


////////////////////////////////////////
//ALDS1_14_D:   Multiple String Matching
//Aho-Corasick????????????????????????MLE??????TLE?????£????????§???
//Suffix-Array????????????
////////////////////////////////////////

//#define debug //*******************************************************************************************************************************************
#ifdef debug
#include <chrono>
#endif

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
//#include <map>
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream
#include <iterator> //insert_iterator::inserter


//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert

using namespace std;


#define dout cout
//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //*******************************************************************************************************************************************
#ifdef OUTPUTFILE
#define dout outputfile
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif


#define din cin
//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILE???.
//#define INPUTFILE "input.txt" //*******************************************************************************************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif

#define scan(A) scanf("%d", &(A))
#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl
//#define dispAll(A,n) cout << #A << " = "; rep(j, 0, (n)) {cout << setw(3) << A[j] << " ";} cout << endl

#define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1
#define p(i) (i)/2
#define l(i) (i)*2
#define r(i) (i)*2+1

int dx[] = {1,-1, 0, 0, 1, 1,-1,-1}; //???????????????????????????????¨??????????????????????????????????
int dy[] = {0, 0,-1, 1,-1, 1, 1,-1};

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long ull;

const int INF = (int)2e9+10;
const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow.
const ull INF_ULL = (ull)1e19-1ULL;
const int NONE = -1;
const ll MOD = (ll)1e9+7; //??§???????´???°?????£??¨??¨????????°????????????10???7??????

const int N_MAX = 1000010; //num of vertex or element
const int M_MAX = 10010; //num of edge
const int DATA_MAX = 1010;

int N;

char T[N_MAX];
int SA[N_MAX];
int Rank[N_MAX];
int tmp[N_MAX];
int k;

int Q;
char* P[M_MAX];
vi placeOfP[M_MAX];

#ifdef debug
char subT[N_MAX];
#endif

bool compare_sa(int i, int j) { //compare Rank(i, i+k) & Rank(j, j+k)
    
    if(Rank[i]!=Rank[j]) return Rank[i] < Rank[j];
    else {
        int rank_i = (i+k<N ? Rank[i+k] : -1);
        int rank_j = (j+k<N ? Rank[j+k] : -1);
        return rank_i < rank_j;
    }
    
}



#ifdef debug
void subStr(int i, int k) { //subT = T[i ... i+k]
    strncpy(subT, T+i, k);
    subT[k] = '\0';
}



void display() {
    dout << "-----\n";
    disp(k);
    
    
    rep(i,0,N) {
        
        dout << " i = ";
        disP(i);
        dout << " : SA[i] = ";
        disP(SA[i]);
        dout << " ( ";
        subStr(SA[i],k); disP(subT);
        dout << " ) , Rank = ";
        disP(Rank[SA[i]]);
        dout << endl;
    }
    
    dout << "-----\n";
    dout << "  i  Rank[i]   Rank[i+k]\n";
    rep(i,0,N) {
        disP(i);
        disP(Rank[i]);
        dout << " ( ";
        subStr(i, k); disP(subT);
        dout << " ) ";
        disP( i+k < N ? Rank[i+k] : -1);
        dout << " ( ";
        subStr(i+k, k); disP(subT);
        dout << " ) ";
        dout << endl;
    }
}
#endif




void construct_sa() {
    
    //initialize
    k = 1;
    rep(i,0,N) {
        SA[i] = i;
        Rank[i] = T[i]; //k=1?????¨??????Rank[i]=ASCII Code of T[i]
    }
    
    for(k=1; k<N; k*=2) {
#ifdef debug
        display();
#endif
        
        sort(SA, SA+N, compare_sa);
        
    
        tmp[ SA[0] ] = 0;
        rep(i,1,N) {
            tmp[ SA[i] ] = tmp[ SA[i-1] ] + compare_sa(SA[i-1], SA[i]); //1?????????k???????????§???Rank?????????????????°????????????????¬????????????§???Rank??????????????????
        }
        
        rep(i,0,N) Rank[i] = tmp[i]; //??????????????§?????§????¬????k(=2k)???Rank????¨???????????????????
        
    }
    
}


void binarySearch_P_from_SA() {

    rep(i,0,Q) {
        
        int lenP = strlen(P[i]);
        
        int left = 0;
        int right = N-1;
        int mid;
        
        while(left <= right) {
            mid = left + (right - left) / 2;
            
            if( strncmp(P[i],T+SA[mid],lenP) == 0 ) {
                placeOfP[i].push_back(1);
                break;
            }
            else if(strncmp(P[i],T+SA[mid],lenP) < 0) right = mid - 1;
            else left = mid + 1;
        }
        
    }
    
}




int main() {
    
    //cin, cout????????????  ?????¨??????cin?????????????????¨??¨cin??§???scanf?????????????????¨??¨scanf??§??±?????????????????????
    cin.tie(0); //cin??¨cout??????????????????
    ios::sync_with_stdio(false); //iostream??¨stdio??????????????????
    
    //read input data
    scanf("%s", T);
    N = strlen(T);
    
    scanf("%d ", &Q);
    rep(i,0,Q) {
        P[i] = (char *)malloc(sizeof(char)*DATA_MAX);
        scanf("%s", P[i]);
    }
    
#ifdef debug
    disp(T);
    disp(N);
    rep(i,0,Q) { disP(P[i]); disp(strlen(P[i])); }
#endif
    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //start timer
    auto startTime = chrono::system_clock::now();
#endif
    //------------------------------------------------------------------------------------------
    
    
    //Suffix-Array Algorithm
    construct_sa();
    
    binarySearch_P_from_SA();
    
    
    
    
    
    
#ifdef debug
    dout << "=====================================\n";
    rep(i,0,Q) {
        disP(P[i]); dout << " : ";
        rep(j,0,placeOfP[i].size()) {
            disP(placeOfP[i][j]);
        }
        dout << endl;
    }
    dout << "=====================================\n";
#endif
    
    rep(i,0,Q) {
        printf("%d\n", placeOfP[i].size()!=0);
    }
    
    

    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //stop timer
    auto endTime = chrono::system_clock::now();
    auto dur = endTime - startTime;
    auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
    dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
#endif
    //------------------------------------------------------------------------------------------
    
#ifdef INPUTFILE
    inputfile.close();
#endif
    
#ifdef OUTPUTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}
### Prompt

Your challenge is to write 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
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// ?????¢
// XCode??§???EOF??\??????Ctrl+D
// ?\???Alt+\
// ans???????§?INT?????????2,147,483,647????¶????????????¨??????????????§long long?????£???????????????????????????
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


////////////////////////////////////////
//ALDS1_14_D:   Multiple String Matching
//Aho-Corasick????????????????????????MLE??????TLE?????£????????§???
//Suffix-Array????????????
////////////////////////////////////////

//#define debug //*******************************************************************************************************************************************
#ifdef debug
#include <chrono>
#endif

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
//#include <map>
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream
#include <iterator> //insert_iterator::inserter


//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert

using namespace std;


#define dout cout
//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //*******************************************************************************************************************************************
#ifdef OUTPUTFILE
#define dout outputfile
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif


#define din cin
//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILE???.
//#define INPUTFILE "input.txt" //*******************************************************************************************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif

#define scan(A) scanf("%d", &(A))
#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl
//#define dispAll(A,n) cout << #A << " = "; rep(j, 0, (n)) {cout << setw(3) << A[j] << " ";} cout << endl

#define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1
#define p(i) (i)/2
#define l(i) (i)*2
#define r(i) (i)*2+1

int dx[] = {1,-1, 0, 0, 1, 1,-1,-1}; //???????????????????????????????¨??????????????????????????????????
int dy[] = {0, 0,-1, 1,-1, 1, 1,-1};

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long ull;

const int INF = (int)2e9+10;
const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow.
const ull INF_ULL = (ull)1e19-1ULL;
const int NONE = -1;
const ll MOD = (ll)1e9+7; //??§???????´???°?????£??¨??¨????????°????????????10???7??????

const int N_MAX = 1000010; //num of vertex or element
const int M_MAX = 10010; //num of edge
const int DATA_MAX = 1010;

int N;

char T[N_MAX];
int SA[N_MAX];
int Rank[N_MAX];
int tmp[N_MAX];
int k;

int Q;
char* P[M_MAX];
vi placeOfP[M_MAX];

#ifdef debug
char subT[N_MAX];
#endif

bool compare_sa(int i, int j) { //compare Rank(i, i+k) & Rank(j, j+k)
    
    if(Rank[i]!=Rank[j]) return Rank[i] < Rank[j];
    else {
        int rank_i = (i+k<N ? Rank[i+k] : -1);
        int rank_j = (j+k<N ? Rank[j+k] : -1);
        return rank_i < rank_j;
    }
    
}



#ifdef debug
void subStr(int i, int k) { //subT = T[i ... i+k]
    strncpy(subT, T+i, k);
    subT[k] = '\0';
}



void display() {
    dout << "-----\n";
    disp(k);
    
    
    rep(i,0,N) {
        
        dout << " i = ";
        disP(i);
        dout << " : SA[i] = ";
        disP(SA[i]);
        dout << " ( ";
        subStr(SA[i],k); disP(subT);
        dout << " ) , Rank = ";
        disP(Rank[SA[i]]);
        dout << endl;
    }
    
    dout << "-----\n";
    dout << "  i  Rank[i]   Rank[i+k]\n";
    rep(i,0,N) {
        disP(i);
        disP(Rank[i]);
        dout << " ( ";
        subStr(i, k); disP(subT);
        dout << " ) ";
        disP( i+k < N ? Rank[i+k] : -1);
        dout << " ( ";
        subStr(i+k, k); disP(subT);
        dout << " ) ";
        dout << endl;
    }
}
#endif




void construct_sa() {
    
    //initialize
    k = 1;
    rep(i,0,N) {
        SA[i] = i;
        Rank[i] = T[i]; //k=1?????¨??????Rank[i]=ASCII Code of T[i]
    }
    
    for(k=1; k<N; k*=2) {
#ifdef debug
        display();
#endif
        
        sort(SA, SA+N, compare_sa);
        
    
        tmp[ SA[0] ] = 0;
        rep(i,1,N) {
            tmp[ SA[i] ] = tmp[ SA[i-1] ] + compare_sa(SA[i-1], SA[i]); //1?????????k???????????§???Rank?????????????????°????????????????¬????????????§???Rank??????????????????
        }
        
        rep(i,0,N) Rank[i] = tmp[i]; //??????????????§?????§????¬????k(=2k)???Rank????¨???????????????????
        
    }
    
}


void binarySearch_P_from_SA() {

    rep(i,0,Q) {
        
        int lenP = strlen(P[i]);
        
        int left = 0;
        int right = N-1;
        int mid;
        
        while(left <= right) {
            mid = left + (right - left) / 2;
            
            if( strncmp(P[i],T+SA[mid],lenP) == 0 ) {
                placeOfP[i].push_back(1);
                break;
            }
            else if(strncmp(P[i],T+SA[mid],lenP) < 0) right = mid - 1;
            else left = mid + 1;
        }
        
    }
    
}




int main() {
    
    //cin, cout????????????  ?????¨??????cin?????????????????¨??¨cin??§???scanf?????????????????¨??¨scanf??§??±?????????????????????
    cin.tie(0); //cin??¨cout??????????????????
    ios::sync_with_stdio(false); //iostream??¨stdio??????????????????
    
    //read input data
    scanf("%s", T);
    N = strlen(T);
    
    scanf("%d ", &Q);
    rep(i,0,Q) {
        P[i] = (char *)malloc(sizeof(char)*DATA_MAX);
        scanf("%s", P[i]);
    }
    
#ifdef debug
    disp(T);
    disp(N);
    rep(i,0,Q) { disP(P[i]); disp(strlen(P[i])); }
#endif
    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //start timer
    auto startTime = chrono::system_clock::now();
#endif
    //------------------------------------------------------------------------------------------
    
    
    //Suffix-Array Algorithm
    construct_sa();
    
    binarySearch_P_from_SA();
    
    
    
    
    
    
#ifdef debug
    dout << "=====================================\n";
    rep(i,0,Q) {
        disP(P[i]); dout << " : ";
        rep(j,0,placeOfP[i].size()) {
            disP(placeOfP[i][j]);
        }
        dout << endl;
    }
    dout << "=====================================\n";
#endif
    
    rep(i,0,Q) {
        printf("%d\n", placeOfP[i].size()!=0);
    }
    
    

    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //stop timer
    auto endTime = chrono::system_clock::now();
    auto dur = endTime - startTime;
    auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
    dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
#endif
    //------------------------------------------------------------------------------------------
    
#ifdef INPUTFILE
    inputfile.close();
#endif
    
#ifdef OUTPUTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}
```