Finding Patterns#2603

Finding Patterns

1 second
128 megabytes

Given a string and a set of patterns, determine for each pattern whether it occurs in the string.

Input

The first line contains a string of length n~(1 \le n \le 10^5).

The second line contains an integer k~(1 \le k \le 5 \cdot 10^5) — the number of patterns. Each of the next lines contains one pattern. The total length of all patterns does not exceed 5 \cdot 10^5.

The string and the patterns consist of lowercase Latin letters '' - ''.

Output

For each pattern, print "YES" if it occurs in the string, and "NO" otherwise.

Examples

Example 1

Loading
Loading