String Search 

Determine whether a text T includes a pattern P. Your program should answer for given queries consisting of Pi.

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 Pi are given respectively.

aabaaa
4
aa
ba
bb
xyz

1
1
0
0

Constraints

• 1 ≤ length of T ≤ 1000000
• 1 ≤ length of Pi ≤ 1000
• 1 ≤ Q ≤ 10000
• The input consists of alphabetical characters and digits