Description

When looking up a word in an English dictionary, people may not know the exact spelling and only know an incorrect approximate spelling. This can be frustrating and waste a lot of time. An electronic dictionary with fuzzy search can help: the user enters a string, and the dictionary returns a few words with the minimum edit distance to that string for the user to choose from.

The edit distance between string $a$ and string $b$ is defined as the minimum number of the following editing operations needed to transform $a$ into $b$ or $b$ into $a$:

1. Delete a letter at some position in the string.
2. Insert a letter at some position in the string.
3. Replace the letter at some position in the string with another letter.

The JSOI team is developing an electronic dictionary. You need to help implement a counting module for the fuzzy search function: for a query string, if it is a word, return $-1$; if it is not a word, return how many words in the dictionary have edit distance $1$ from it.

Input Format

The first line contains two positive integers $N$ and $M$.

The next $N$ lines each contain one string; the $(i+1)$-th line is the word $W_i$, with length from $1$ to $20$.

Then the next $M$ lines each contain one string; the $(i+N+1)$-th line is the query string $Q_i$. The length of each query string is from $1$ to $20$. Each of $W_i$ and $Q_i$ consists of lowercase letters. There are no extra spaces in the input.

Output Format

Output $M$ lines. The $i$-th line contains an integer $X_i$:

• $X_i = -1$ means $Q_i$ is a word in the dictionary.
• Otherwise, $X_i$ is the number of dictionary words whose edit distance from $Q_i$ is $1$.

4 3
abcd
abcde
aabc
abced
abcd
abc
abcdd

-1
2
3

Hint

Sample explanation:

• abcd appears in the word list.
• The edit distance between abc and each of abcd and aabc is $1$.
• The edit distance between abcdd and each of abcd, abcde, and abced is $1$.

Constraints and Notes:

• All words are distinct, but query strings may repeat.
• For $50\%$ of the constraints, $N, M \le 10^3$.
• For $100\%$ of the constraints, $N, M \le 10^4$.

Translated by ChatGPT 5