Search Multiple Strings

Given a long text t and n strings , you are asked to check for each of the strings if they are a substring of t.

😎

Pro Tip If you need to increase the probability that the two substrings are actually equal to each other using hashes, you might consider calculating several hashes using different prime numbers and different modulo numbers to make sure the hashes are actually equal. This way, you’d compare a tuple of hashes to another tuple of hashes.

Input

The first line of the input contains the text t (1 ≤ |t| ≤ ).

The next line contains a single integer n (1 ≤ n ≤ ).

The next n lines contain strings (1 ≤ || ≤ min(50, |t|)).

Output

The program should print n lines. Each line should contain Yes if the corresponding string is a substring of t, and No otherwise.

Examples

Input	Output
habababohabo 3 ba yoyo ababoha	Yes No Yes

Search Multiple Strings

Input

Output

Examples

Constraints

To check your solution you need to sign in

Sign in to continue