Fuzzy Matching

Imagine you are one of the earliest engineers at Google, and you need to implement a feature on Google Search that checks whether the user input is present in the database or not.
As you’re just starting to work on the search algorithm, you’re playing with a test dataset that only contains text with 3 lowercase letters a, b, and c.
notion image
There are n strings in the database and you are given k queries. You want to make the search engine both performant and fault-tolerant, so you’ve decided to allow at most 1 misspelled letter.
For each query string, the program should check if the query string is present in the database while allowing at most one misspelled character (no adding or removing characters).

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000).
The next n lines contain the strings present in the database . It’s guaranteed that the sum of the lengths of the strings in the database doesn’t exceed 100 000.
The first line of the input contains a single integer k (1 ≤ k ≤ 100 000) the number of queries.
The next k lines contain the query strings . It’s guaranteed that the sum of the lengths of the query strings doesn’t exceed 100 000.

Output

For each of the query strings, the program should print Yes if it exists in the database and No otherwise, while allowing for at most 1 misspelled letter.

Examples

Input
Output
2 aaabccc aaaaaac 4 aaabccc aabaccc aaaaaab aaaaaaaab
Yes No Yes No
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue