Suffix Tree - Dictionary Queries
hard
You are given a string S, and Q queries. Each query consist of a string T. You have to determine if T is a substring of S.
Constraints
|S| <= 10^5 Q <= 1000 |T| <= 1000
Format
Input
Input consist of A string S and an integer Q followed by Q strings
Output
If T is a substring of S, print "y", else print "n"
Example
Sample Input
2
abcdefghABCDEFGH
2
abc
abAB
xyz
1
xyz
Sample Output
y
n
y