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