#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
template<class T>
struct SparseTable{
	vector<T> st[21];
	void Init(int N,vector<T> &data){
		st[0].resize(N);
		int h = 1;
		while ((1 << h) < N){
			st[h].resize(N - (1 << h) + 1);
			h++;
		}
		for(int i=0;i<N;i++){
			st[0][i] = data[i];
		}
		for(int j=1;j<=h;j++){
			for(int i=0;i<N-(1<<j)+1;i++){
				st[j][i] = min(st[j-1][i],st[j-1][i + (1 << (j - 1))]);
			}
		}
	}
	inline int TopBit(int t){
		return 31-__builtin_clz(t);
	}
	T GetMin(int b,int e){
        e++;
		int diff = TopBit(e-b);
		return min(st[diff][b], st[diff][e - (1 << diff)]);
	}
};
struct StringManager{
	const vector<int> S;
	const int maxChar;
	const int N;
	vector<int> SuffixArray;
	vector<int> LCPArray;
	SparseTable<int> LCARMQ;
	StringManager(const vector<int>& data_,int c)
        : S(data_), maxChar(c), N(data_.size()) {
    }
	static vector<int> StringToIntArray(string s){
		vector<int> ans(s.length());
		for(int i=0;i<s.length();i++){
			ans[i] = s[i] - 'a';
		}
		return ans;
	}
	StringManager(string s)
        : S(StringToIntArray(s)), maxChar(26), N(s.length()) {
    }
	void SAIS(){
		//文字列を格納
		vector<int> Sbuffer(N*2+10);
		//S-typeかL-typeか
		vector<bool> SLbuffer(N*2+10);
		//LMS−typeなら何番目か
		vector<int> rLMSbuffer(N*2+10);
		//LMS−typeの場所
		vector<int> LMSbuffer(N+100);
		//Binの境界をを格納
		vector<int> Binbuffer(maxChar+N+100);
		//Binをどこまでうめたか必要な時に使う
		vector<int> BinPointerbuffer(maxChar+N+100);
		vector<tuple<int,int,int,int,int,int>> WorkInformation(100);
		vector<int> Ansbuffer(N*2+10,-1);
		for(int i=0;i<N;i++){
			Sbuffer[i] = S[i]+1;
		}
		Sbuffer[N] = 0;
		WorkInformation[0] = make_tuple(0,0,0,maxChar+1,N+1,0);
		int WorkPointer = 0;
		while(WorkPointer >= 0){
			const int Spointer = get<0>(WorkInformation[WorkPointer]);
			const int Binpointer = get<1>(WorkInformation[WorkPointer]);
			const int LMSpointer = get<2>(WorkInformation[WorkPointer]);
			const int CharNum = get<3>(WorkInformation[WorkPointer]);
			const int SLength = get<4>(WorkInformation[WorkPointer]);
			int LMSnum = get<5>(WorkInformation[WorkPointer]);
			WorkPointer--;
			//最初に問題を解く時
			if(LMSnum == 0){
				//S-typeかL-typeかを計算
				SLbuffer[Spointer+SLength-1] = true;
				for(int i=SLength-2;i>=0;i--){
					if(Sbuffer[Spointer+i] < Sbuffer[Spointer+i+1]){
						SLbuffer[Spointer+i] = true;
					}
					else if(Sbuffer[Spointer+i] > Sbuffer[Spointer+i+1]){
						SLbuffer[Spointer+i] = false;
					}
					else{
						SLbuffer[Spointer+i] = SLbuffer[Spointer+i+1];
					}
				}
				//LMS-typeを格納
				for(int i=1;i<SLength;i++){
					if(SLbuffer[Spointer+i] && !SLbuffer[Spointer+i-1]){
						LMSbuffer[LMSpointer+LMSnum] = i;
						LMSnum++;
						rLMSbuffer[Spointer+i] = LMSnum;
					}
				}
				//Binbufferを計算
				for(int i=0;i<SLength;i++){
					Binbuffer[Binpointer+Sbuffer[Spointer+i]+1]++;
				}
				for(int i=1;i<CharNum;i++){
					Binbuffer[Binpointer+i+1] += Binbuffer[Binpointer+i];
				}
				//LMS-typeをそれぞれのbinごとに後ろから入れていく　同時に頭文字が同じLMSが存在するか確認
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i+1]-1;
				}
				bool SameTopCharacterLMSExist = false;
				for(int i=0;i<LMSnum;i++){
					int ch = Sbuffer[Spointer+LMSbuffer[LMSpointer+i]];
					Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = LMSbuffer[LMSpointer+i];
					SameTopCharacterLMSExist |= BinPointerbuffer[Binpointer+ch] != Binbuffer[Binpointer+ch+1]-1;
					BinPointerbuffer[Binpointer+ch]--;
				}
				//LMS-typeを基にL-typeを入れていく
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i];
				}
				for(int i=0;i<SLength;i++){
					int v = Ansbuffer[Spointer+i];
					if(v > 0){
						if(!SLbuffer[Spointer+v-1]){
							int ch = Sbuffer[Spointer+v-1];
							Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = v-1;
							BinPointerbuffer[Binpointer+ch]++;
						}
					}
				}
				//L-typeを基にS-typeを入れていく
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i+1]-1;
				}
				for(int i=SLength-1;i>=0;i--){
					int v = Ansbuffer[Spointer+i];
					if(v != 0){
						if(SLbuffer[Spointer+v-1]){
							int ch = Sbuffer[Spointer+v-1];
							Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = v-1;
							BinPointerbuffer[Binpointer+ch]--;
						}
					}
				}
				//LMS-typeの順番が間違っている可能性のある時
				if(SameTopCharacterLMSExist){
					int newSpointer = Spointer+SLength;
					//新しい文字列を作る
					int beforeLMSString = -1;
					int LMSStringKind = -1;
					for(int i=0;i<SLength;i++){
						int v = Ansbuffer[Spointer+i];
						if(rLMSbuffer[Spointer+v] != 0){
							int afterLMSString = rLMSbuffer[Spointer+v]-1;
							//種類が違うか判断　最初はダミー文字で他と一致しないことに注意
							if(LMSStringKind > 0){
								int beforeLMSStringF = LMSbuffer[LMSpointer+beforeLMSString];
								int beforeLMSStringT = LMSbuffer[LMSpointer+beforeLMSString+1];
								int afterLMSStringF = LMSbuffer[LMSpointer+afterLMSString];
								int afterLMSStringT = LMSbuffer[LMSpointer+afterLMSString+1];
								if(beforeLMSStringT - beforeLMSStringF == afterLMSStringT - afterLMSStringF){
									int c = beforeLMSStringT - beforeLMSStringF;
									for(int i=0;i<=c;i++){
										if(Sbuffer[Spointer+beforeLMSStringF+i] != Sbuffer[Spointer+afterLMSStringF+i]){
											LMSStringKind++;
											break;
										}
									}
									LMSStringKind--;
								}
							}
							LMSStringKind++;
							Sbuffer[newSpointer+rLMSbuffer[Spointer+v]-1] = LMSStringKind;
							beforeLMSString = afterLMSString;
						}
					}
					LMSStringKind++;
					WorkInformation[WorkPointer+1] = make_tuple(Spointer,Binpointer,LMSpointer,CharNum,SLength,LMSnum);
					WorkInformation[WorkPointer+2] = make_tuple(Spointer+SLength,Binpointer+CharNum+1,LMSpointer+LMSnum,LMSStringKind,LMSnum,0);
					WorkPointer += 2;
				}
			}
			//再帰から戻った後
			else{
				int newSpointer = Spointer+SLength;
				//Ansbufferを初期化
				for(int i=Spointer;i<newSpointer;i++){
					Ansbuffer[i] = -1;
				}
				//LMS-typeをそれぞれのbinごとに後ろから入れていく
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i+1]-1;
				}
				for(int i=LMSnum-1;i>=0;i--){
					int ch = Sbuffer[Spointer+LMSbuffer[LMSpointer+Ansbuffer[newSpointer+i]]];
					Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = LMSbuffer[LMSpointer+Ansbuffer[newSpointer+i]];
					BinPointerbuffer[Binpointer+ch]--;
				}
				//LMS-typeを基にL-typeを入れていく
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i];
				}
				for(int i=0;i<SLength;i++){
					int v = Ansbuffer[Spointer+i];
					if(v > 0){
						if(!SLbuffer[Spointer+v-1]){
							int ch = Sbuffer[Spointer+v-1];
							Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = v-1;
							BinPointerbuffer[Binpointer+ch]++;
						}
					}
				}
				//L-typeを基にS-typeを入れていく
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i+1]-1;
				}
				for(int i=SLength-1;i>=0;i--){
					int v = Ansbuffer[Spointer+i];
					if(v != 0){
						if(SLbuffer[Spointer+v-1]){
							int ch = Sbuffer[Spointer+v-1];
							Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = v-1;
							BinPointerbuffer[Binpointer+ch]--;
						}
					}
				}
			}
		}
		SuffixArray.resize(N);
		for(int i=0;i<N;i++){
			SuffixArray[i] = Ansbuffer[i+1];
		}
	}
	void CalculateLCP(){
		if(SuffixArray.size() == 0){
			SAIS();
		}
		vector<int> rSuffixrray(N);
		LCPArray.resize(N);
		for(int i=0;i<N;i++){
			rSuffixrray[SuffixArray[i]] = i;
		}
		int lcp = 0;
		for(int p=0;p<N;p++){
			int i = rSuffixrray[p];
			if(i > 0){
				while(p+lcp < N && SuffixArray[i-1]+lcp < N && S[p+lcp] == S[SuffixArray[i-1]+lcp]){
					lcp++;
				}
			}
			else{
				lcp = 0;
			}
			LCPArray[i] = lcp;
			if(lcp > 0){
				lcp--;
			}
		}
		LCARMQ.Init(N,LCPArray);
	}
	//SuffixArray[x]とSuffixArray[y]のLCA x < y
	int LCP(int x,int y){
		return LCARMQ.GetMin(x+1,y);
	}
	int find(string s){
		return find(StringToIntArray(s));
	}
	int find(vector<int> key){
		int M = key.size();
		int bf = 0;
		int bl = N-1;
		//どこまでkeyと一致していると言えるか
		int bfkey = 0;//これはbfの1個左と
		int blkey = 0;
		while(blkey < M && SuffixArray[bl]+blkey < N && key[blkey] == S[SuffixArray[bl]+blkey]){
			blkey++;
		}
		if(blkey == M){
			return SuffixArray[bl];
		}
		if(SuffixArray[bl]+blkey == N || S[SuffixArray[bl]+blkey] < key[blkey]){
			return -1;
		}
		while(bf != bl){
			int bc = (bf+bl)/2;
			int bfbc = LCP(bf-1,bc);
			int blbc = LCP(bc,bl);
			if(bfbc >= blbc){
				if(bfkey < bfbc){
					bf = bc+1;
				}
				else if(bfkey > bfbc){
					bl = bc;
					blkey = bfbc;
				}
				else{
					int bckey = bfkey;
					while(bckey < M && SuffixArray[bc]+bckey < N && key[bckey] == S[SuffixArray[bc]+bckey]){
						bckey++;
					}
					if(bckey == M){
						return SuffixArray[bc];
					}
					if(SuffixArray[bc]+bckey == N || S[SuffixArray[bc]+bckey] < key[bckey]){
						bf = bc+1;
						bfkey = bckey;
					}
					else{
						bl = bc;
						blkey = bckey;
					}	
				}
			}
			else{
				if(blkey < blbc){
					bl = bc;
				}
				else if(blkey > blbc){
					bf = bc+1;
					bfkey = blbc;
				}
				else{
					int bckey = blkey;
					while(bckey < M && SuffixArray[bc]+bckey < N && key[bckey] == S[SuffixArray[bc]+bckey]){
						bckey++;
					}
					if(bckey == M){
						return bc;
					}
					if(SuffixArray[bc]+bckey == N || S[SuffixArray[bc]+bckey] < key[bckey]){
						bf = bc+1;
						bfkey = bckey;
					}
					else{
						bl = bc;
						blkey = bckey;
					}	
				}
			}
		}
		if(blkey == M){
			return SuffixArray[bl];
		}
		else{
			return -1;
		}
	}
};
void Calc(){
	string s = res();
	vector<int> ss(s.length());
	for(int i=0;i<s.length();i++){
		if('a' <= s[i] && s[i] <= 'z'){
			ss[i] = s[i] - 'a' + 10;
		}
		else{
			ss[i] = s[i] - '0';
		}
	}
	StringManager S(ss,36);
	int Q = rei();
	S.CalculateLCP();
	for(int query=0;query<Q;query++){
		string qs = res();
		vector<int> qss(qs.length());
		for(int i=0;i<qs.length();i++){
			if('a' <= qs[i] && qs[i] <= 'z'){
				qss[i] = qs[i] - 'a' + 10;
			}
			else{
				qss[i] = qs[i] - '0';
			}
		}
		if(S.find(qss) == -1){
			cout << "0" << endl;
		}
		else{
			cout << "1" << endl;
		}
	}
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

### Prompt

In Cpp, your task is to solve 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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
template<class T>
struct SparseTable{
	vector<T> st[21];
	void Init(int N,vector<T> &data){
		st[0].resize(N);
		int h = 1;
		while ((1 << h) < N){
			st[h].resize(N - (1 << h) + 1);
			h++;
		}
		for(int i=0;i<N;i++){
			st[0][i] = data[i];
		}
		for(int j=1;j<=h;j++){
			for(int i=0;i<N-(1<<j)+1;i++){
				st[j][i] = min(st[j-1][i],st[j-1][i + (1 << (j - 1))]);
			}
		}
	}
	inline int TopBit(int t){
		return 31-__builtin_clz(t);
	}
	T GetMin(int b,int e){
        e++;
		int diff = TopBit(e-b);
		return min(st[diff][b], st[diff][e - (1 << diff)]);
	}
};
struct StringManager{
	const vector<int> S;
	const int maxChar;
	const int N;
	vector<int> SuffixArray;
	vector<int> LCPArray;
	SparseTable<int> LCARMQ;
	StringManager(const vector<int>& data_,int c)
        : S(data_), maxChar(c), N(data_.size()) {
    }
	static vector<int> StringToIntArray(string s){
		vector<int> ans(s.length());
		for(int i=0;i<s.length();i++){
			ans[i] = s[i] - 'a';
		}
		return ans;
	}
	StringManager(string s)
        : S(StringToIntArray(s)), maxChar(26), N(s.length()) {
    }
	void SAIS(){
		//文字列を格納
		vector<int> Sbuffer(N*2+10);
		//S-typeかL-typeか
		vector<bool> SLbuffer(N*2+10);
		//LMS−typeなら何番目か
		vector<int> rLMSbuffer(N*2+10);
		//LMS−typeの場所
		vector<int> LMSbuffer(N+100);
		//Binの境界をを格納
		vector<int> Binbuffer(maxChar+N+100);
		//Binをどこまでうめたか必要な時に使う
		vector<int> BinPointerbuffer(maxChar+N+100);
		vector<tuple<int,int,int,int,int,int>> WorkInformation(100);
		vector<int> Ansbuffer(N*2+10,-1);
		for(int i=0;i<N;i++){
			Sbuffer[i] = S[i]+1;
		}
		Sbuffer[N] = 0;
		WorkInformation[0] = make_tuple(0,0,0,maxChar+1,N+1,0);
		int WorkPointer = 0;
		while(WorkPointer >= 0){
			const int Spointer = get<0>(WorkInformation[WorkPointer]);
			const int Binpointer = get<1>(WorkInformation[WorkPointer]);
			const int LMSpointer = get<2>(WorkInformation[WorkPointer]);
			const int CharNum = get<3>(WorkInformation[WorkPointer]);
			const int SLength = get<4>(WorkInformation[WorkPointer]);
			int LMSnum = get<5>(WorkInformation[WorkPointer]);
			WorkPointer--;
			//最初に問題を解く時
			if(LMSnum == 0){
				//S-typeかL-typeかを計算
				SLbuffer[Spointer+SLength-1] = true;
				for(int i=SLength-2;i>=0;i--){
					if(Sbuffer[Spointer+i] < Sbuffer[Spointer+i+1]){
						SLbuffer[Spointer+i] = true;
					}
					else if(Sbuffer[Spointer+i] > Sbuffer[Spointer+i+1]){
						SLbuffer[Spointer+i] = false;
					}
					else{
						SLbuffer[Spointer+i] = SLbuffer[Spointer+i+1];
					}
				}
				//LMS-typeを格納
				for(int i=1;i<SLength;i++){
					if(SLbuffer[Spointer+i] && !SLbuffer[Spointer+i-1]){
						LMSbuffer[LMSpointer+LMSnum] = i;
						LMSnum++;
						rLMSbuffer[Spointer+i] = LMSnum;
					}
				}
				//Binbufferを計算
				for(int i=0;i<SLength;i++){
					Binbuffer[Binpointer+Sbuffer[Spointer+i]+1]++;
				}
				for(int i=1;i<CharNum;i++){
					Binbuffer[Binpointer+i+1] += Binbuffer[Binpointer+i];
				}
				//LMS-typeをそれぞれのbinごとに後ろから入れていく　同時に頭文字が同じLMSが存在するか確認
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i+1]-1;
				}
				bool SameTopCharacterLMSExist = false;
				for(int i=0;i<LMSnum;i++){
					int ch = Sbuffer[Spointer+LMSbuffer[LMSpointer+i]];
					Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = LMSbuffer[LMSpointer+i];
					SameTopCharacterLMSExist |= BinPointerbuffer[Binpointer+ch] != Binbuffer[Binpointer+ch+1]-1;
					BinPointerbuffer[Binpointer+ch]--;
				}
				//LMS-typeを基にL-typeを入れていく
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i];
				}
				for(int i=0;i<SLength;i++){
					int v = Ansbuffer[Spointer+i];
					if(v > 0){
						if(!SLbuffer[Spointer+v-1]){
							int ch = Sbuffer[Spointer+v-1];
							Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = v-1;
							BinPointerbuffer[Binpointer+ch]++;
						}
					}
				}
				//L-typeを基にS-typeを入れていく
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i+1]-1;
				}
				for(int i=SLength-1;i>=0;i--){
					int v = Ansbuffer[Spointer+i];
					if(v != 0){
						if(SLbuffer[Spointer+v-1]){
							int ch = Sbuffer[Spointer+v-1];
							Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = v-1;
							BinPointerbuffer[Binpointer+ch]--;
						}
					}
				}
				//LMS-typeの順番が間違っている可能性のある時
				if(SameTopCharacterLMSExist){
					int newSpointer = Spointer+SLength;
					//新しい文字列を作る
					int beforeLMSString = -1;
					int LMSStringKind = -1;
					for(int i=0;i<SLength;i++){
						int v = Ansbuffer[Spointer+i];
						if(rLMSbuffer[Spointer+v] != 0){
							int afterLMSString = rLMSbuffer[Spointer+v]-1;
							//種類が違うか判断　最初はダミー文字で他と一致しないことに注意
							if(LMSStringKind > 0){
								int beforeLMSStringF = LMSbuffer[LMSpointer+beforeLMSString];
								int beforeLMSStringT = LMSbuffer[LMSpointer+beforeLMSString+1];
								int afterLMSStringF = LMSbuffer[LMSpointer+afterLMSString];
								int afterLMSStringT = LMSbuffer[LMSpointer+afterLMSString+1];
								if(beforeLMSStringT - beforeLMSStringF == afterLMSStringT - afterLMSStringF){
									int c = beforeLMSStringT - beforeLMSStringF;
									for(int i=0;i<=c;i++){
										if(Sbuffer[Spointer+beforeLMSStringF+i] != Sbuffer[Spointer+afterLMSStringF+i]){
											LMSStringKind++;
											break;
										}
									}
									LMSStringKind--;
								}
							}
							LMSStringKind++;
							Sbuffer[newSpointer+rLMSbuffer[Spointer+v]-1] = LMSStringKind;
							beforeLMSString = afterLMSString;
						}
					}
					LMSStringKind++;
					WorkInformation[WorkPointer+1] = make_tuple(Spointer,Binpointer,LMSpointer,CharNum,SLength,LMSnum);
					WorkInformation[WorkPointer+2] = make_tuple(Spointer+SLength,Binpointer+CharNum+1,LMSpointer+LMSnum,LMSStringKind,LMSnum,0);
					WorkPointer += 2;
				}
			}
			//再帰から戻った後
			else{
				int newSpointer = Spointer+SLength;
				//Ansbufferを初期化
				for(int i=Spointer;i<newSpointer;i++){
					Ansbuffer[i] = -1;
				}
				//LMS-typeをそれぞれのbinごとに後ろから入れていく
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i+1]-1;
				}
				for(int i=LMSnum-1;i>=0;i--){
					int ch = Sbuffer[Spointer+LMSbuffer[LMSpointer+Ansbuffer[newSpointer+i]]];
					Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = LMSbuffer[LMSpointer+Ansbuffer[newSpointer+i]];
					BinPointerbuffer[Binpointer+ch]--;
				}
				//LMS-typeを基にL-typeを入れていく
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i];
				}
				for(int i=0;i<SLength;i++){
					int v = Ansbuffer[Spointer+i];
					if(v > 0){
						if(!SLbuffer[Spointer+v-1]){
							int ch = Sbuffer[Spointer+v-1];
							Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = v-1;
							BinPointerbuffer[Binpointer+ch]++;
						}
					}
				}
				//L-typeを基にS-typeを入れていく
				for(int i=0;i<CharNum;i++){
					BinPointerbuffer[Binpointer+i] = Binbuffer[Binpointer+i+1]-1;
				}
				for(int i=SLength-1;i>=0;i--){
					int v = Ansbuffer[Spointer+i];
					if(v != 0){
						if(SLbuffer[Spointer+v-1]){
							int ch = Sbuffer[Spointer+v-1];
							Ansbuffer[Spointer+BinPointerbuffer[Binpointer+ch]] = v-1;
							BinPointerbuffer[Binpointer+ch]--;
						}
					}
				}
			}
		}
		SuffixArray.resize(N);
		for(int i=0;i<N;i++){
			SuffixArray[i] = Ansbuffer[i+1];
		}
	}
	void CalculateLCP(){
		if(SuffixArray.size() == 0){
			SAIS();
		}
		vector<int> rSuffixrray(N);
		LCPArray.resize(N);
		for(int i=0;i<N;i++){
			rSuffixrray[SuffixArray[i]] = i;
		}
		int lcp = 0;
		for(int p=0;p<N;p++){
			int i = rSuffixrray[p];
			if(i > 0){
				while(p+lcp < N && SuffixArray[i-1]+lcp < N && S[p+lcp] == S[SuffixArray[i-1]+lcp]){
					lcp++;
				}
			}
			else{
				lcp = 0;
			}
			LCPArray[i] = lcp;
			if(lcp > 0){
				lcp--;
			}
		}
		LCARMQ.Init(N,LCPArray);
	}
	//SuffixArray[x]とSuffixArray[y]のLCA x < y
	int LCP(int x,int y){
		return LCARMQ.GetMin(x+1,y);
	}
	int find(string s){
		return find(StringToIntArray(s));
	}
	int find(vector<int> key){
		int M = key.size();
		int bf = 0;
		int bl = N-1;
		//どこまでkeyと一致していると言えるか
		int bfkey = 0;//これはbfの1個左と
		int blkey = 0;
		while(blkey < M && SuffixArray[bl]+blkey < N && key[blkey] == S[SuffixArray[bl]+blkey]){
			blkey++;
		}
		if(blkey == M){
			return SuffixArray[bl];
		}
		if(SuffixArray[bl]+blkey == N || S[SuffixArray[bl]+blkey] < key[blkey]){
			return -1;
		}
		while(bf != bl){
			int bc = (bf+bl)/2;
			int bfbc = LCP(bf-1,bc);
			int blbc = LCP(bc,bl);
			if(bfbc >= blbc){
				if(bfkey < bfbc){
					bf = bc+1;
				}
				else if(bfkey > bfbc){
					bl = bc;
					blkey = bfbc;
				}
				else{
					int bckey = bfkey;
					while(bckey < M && SuffixArray[bc]+bckey < N && key[bckey] == S[SuffixArray[bc]+bckey]){
						bckey++;
					}
					if(bckey == M){
						return SuffixArray[bc];
					}
					if(SuffixArray[bc]+bckey == N || S[SuffixArray[bc]+bckey] < key[bckey]){
						bf = bc+1;
						bfkey = bckey;
					}
					else{
						bl = bc;
						blkey = bckey;
					}	
				}
			}
			else{
				if(blkey < blbc){
					bl = bc;
				}
				else if(blkey > blbc){
					bf = bc+1;
					bfkey = blbc;
				}
				else{
					int bckey = blkey;
					while(bckey < M && SuffixArray[bc]+bckey < N && key[bckey] == S[SuffixArray[bc]+bckey]){
						bckey++;
					}
					if(bckey == M){
						return bc;
					}
					if(SuffixArray[bc]+bckey == N || S[SuffixArray[bc]+bckey] < key[bckey]){
						bf = bc+1;
						bfkey = bckey;
					}
					else{
						bl = bc;
						blkey = bckey;
					}	
				}
			}
		}
		if(blkey == M){
			return SuffixArray[bl];
		}
		else{
			return -1;
		}
	}
};
void Calc(){
	string s = res();
	vector<int> ss(s.length());
	for(int i=0;i<s.length();i++){
		if('a' <= s[i] && s[i] <= 'z'){
			ss[i] = s[i] - 'a' + 10;
		}
		else{
			ss[i] = s[i] - '0';
		}
	}
	StringManager S(ss,36);
	int Q = rei();
	S.CalculateLCP();
	for(int query=0;query<Q;query++){
		string qs = res();
		vector<int> qss(qs.length());
		for(int i=0;i<qs.length();i++){
			if('a' <= qs[i] && qs[i] <= 'z'){
				qss[i] = qs[i] - 'a' + 10;
			}
			else{
				qss[i] = qs[i] - '0';
			}
		}
		if(S.find(qss) == -1){
			cout << "0" << endl;
		}
		else{
			cout << "1" << endl;
		}
	}
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

```