#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

#pragma warning(disable : 4996)

using namespace std;

vector<int> dat;
vector<int> tmp;

int doubles, lengths;

bool compare_suffix(int i, int j)
{
	if (dat[i] == dat[j])
	{
		int ri = (i + doubles <= lengths ? dat[i + doubles] : -1);
		int rj = (j + doubles <= lengths ? dat[j + doubles] : -1);

		return ri < rj;
	}

	return dat[i] < dat[j];
}

vector<int> suffix_array(string S)
{
	lengths = S.size();

	vector<int> arrays(lengths + 1);

	dat.resize(lengths + 1);
	tmp.resize(lengths + 1);

	for (int i = 0; i <= lengths; i++)
	{
		arrays[i] = i;

		dat[i] = i < lengths ? S[i] : -1;
	}

	for (doubles = 1; doubles <= lengths; doubles <<= 1)
	{
		sort(arrays.begin(), arrays.begin() + lengths + 1, compare_suffix);

		tmp[arrays[0]] = 0;

		for (int i = 1; i <= lengths; i++)
		{
			tmp[arrays[i]] = tmp[arrays[i - 1]] + (compare_suffix(arrays[i - 1], arrays[i]) ? 1 : 0);
		}

		for (int i = 0; i <= lengths; i++)
		{
			dat[i] = tmp[i];
		}
	}

	return arrays;
}

int main()
{
	string S, T; int Q;
	
	cin >> S >> Q;

	vector<int> sa = suffix_array(S);

	for (int i = 0; i < Q; i++)
	{
		cin >> T;

		int l = 0;
		int r = sa.size();

		bool flag = false;

		while (r - l > 1)
		{
			int m = (l + r) / 2;

			string S1 = S.substr(sa[m], T.size());

			if (S1 == T)
			{
				flag = true; break;
			}
			
			if (S1 < T)
			{
				l = m;
			}
			else
			{
				r = m;
			}
		}

		if (flag)
		{
			printf("1\n");
		}
		else
		{
			printf("0\n");
		}
	}

	return 0;
}
### Prompt

Generate 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
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

#pragma warning(disable : 4996)

using namespace std;

vector<int> dat;
vector<int> tmp;

int doubles, lengths;

bool compare_suffix(int i, int j)
{
	if (dat[i] == dat[j])
	{
		int ri = (i + doubles <= lengths ? dat[i + doubles] : -1);
		int rj = (j + doubles <= lengths ? dat[j + doubles] : -1);

		return ri < rj;
	}

	return dat[i] < dat[j];
}

vector<int> suffix_array(string S)
{
	lengths = S.size();

	vector<int> arrays(lengths + 1);

	dat.resize(lengths + 1);
	tmp.resize(lengths + 1);

	for (int i = 0; i <= lengths; i++)
	{
		arrays[i] = i;

		dat[i] = i < lengths ? S[i] : -1;
	}

	for (doubles = 1; doubles <= lengths; doubles <<= 1)
	{
		sort(arrays.begin(), arrays.begin() + lengths + 1, compare_suffix);

		tmp[arrays[0]] = 0;

		for (int i = 1; i <= lengths; i++)
		{
			tmp[arrays[i]] = tmp[arrays[i - 1]] + (compare_suffix(arrays[i - 1], arrays[i]) ? 1 : 0);
		}

		for (int i = 0; i <= lengths; i++)
		{
			dat[i] = tmp[i];
		}
	}

	return arrays;
}

int main()
{
	string S, T; int Q;
	
	cin >> S >> Q;

	vector<int> sa = suffix_array(S);

	for (int i = 0; i < Q; i++)
	{
		cin >> T;

		int l = 0;
		int r = sa.size();

		bool flag = false;

		while (r - l > 1)
		{
			int m = (l + r) / 2;

			string S1 = S.substr(sa[m], T.size());

			if (S1 == T)
			{
				flag = true; break;
			}
			
			if (S1 < T)
			{
				l = m;
			}
			else
			{
				r = m;
			}
		}

		if (flag)
		{
			printf("1\n");
		}
		else
		{
			printf("0\n");
		}
	}

	return 0;
}
```