Code Submission Evaluation System Login

CSES - HIIT Open 2016

HIIT Open 2016

Contest start:2016-05-28 11:00:00
Contest end:2016-05-28 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


DNA sequence

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
Example

Input:
AGGTCAGT
3
GGTC
GGTA
AG


Output:
YES
NO
YES