Multiple String Matching

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

inputFormat

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.

outputFormat

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

样例

aabaaa
4
aa
ba
bb
xyz

1
1
0
0

</p>