Description

Punctuation appeared later than writing, so earlier languages had no punctuation. Now you need to process an article without punctuation.

An article $T$ consists of lowercase letters. A word $W$ also consists of lowercase letters. A dictionary $D$ is a set of words. We say an article $T$ is understandable under a dictionary $D$ if $T$ can be split into several parts and each part is a word in $D$.

For example, if the dictionary $D$ includes the words $\texttt{is}, \texttt{name}, \texttt{what}, \texttt{your}$, then the article whatisyourname is understandable under $D$ because it can be split into 4 words: what, is, your, name, and each word belongs to $D$. The article whatisyouname is not understandable under $D$, but it is understandable under $D' = D \cup \{\texttt{you}\}$. A prefix whatis of this article is also understandable under $D$, and it is the longest prefix that can be understood under $D$.

Given a dictionary $D$, your program needs to determine whether several articles are understandable under $D$, and output the position of the longest prefix that can be understood under $D$.

Input Format

The first line contains two integers $n$ and $m$, indicating that the dictionary $D$ has $n$ words and there are $m$ articles to process.

The next $n$ lines each contain a string $s$, representing a word in the dictionary $D$.

The next $m$ lines each contain a string $t$, representing an article.

Output Format

For each article in the input, output one line with a single integer, the position of the longest prefix that can be understood under the dictionary $D$.

4 3 
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

14
6
0

Hint

Explanation for Sample 1

• For the first query, the entire article whatisyourname can be understood.
• For the second query, the prefix whatis can be understood.
• For the third query, no prefix can be understood.

Constraints

• For $80\%$ of the data, it is guaranteed that $m \leq 20$, $|t| \leq 10^6$.
• For $100\%$ of the data, it is guaranteed that $1 \leq n \leq 20$, $1 \leq m \leq 50$, $1 \leq |s| \leq 20$, $1 \leq |t| \leq 2 \times 10^6$, and both $s$ and $t$ contain only lowercase English letters.

Tips

• Pay attention to the impact of input reading on program efficiency.
• Note that the string lengths marked in Constraints are per-string lengths, not the sum of lengths.

Notes

• The testdata is strengthened; the first $80\%$ is the original testdata.

Translated by ChatGPT 5