- Time limit: 1.00 s
- Memory limit: 256 MB
You are given a DNA sequence of length n. The sequence consists of characters A, C, G and T.
In addition, you are given q queries. In each query your task is to find out if the sequence contains a query sequence as substring.
Input
The first input line contains the sequence of length n. The second input line contains an integer q: the number of queries.
Finally, there are q lines, each containing a query sequence.
All sequences consist of characters A, C, G and T.
Output
For each query, output "YES" if the sequence contains the query sequence as substring, and "NO" otherwise.
Constraints
- 1 \le n,q \le 10^5
- the length of each query sequence is between 1 \ldots 10
Example
Input:
AGGTCAGT 3 GGTC GGTA AG
Output:
YES NO YES