Punctuation marks appeared later than written language, so ancient languages did not have punctuation. You are to process a piece of text that lacks punctuation.

A piece of text $T$ consists of several lowercase letters. A word $W$ also consists of several lowercase letters. A dictionary $D$ is a collection of several words. We say that a piece of text $T$ is "understandable" under a dictionary $D$ if $T$ can be partitioned into several parts, where each part is a word in $D$.

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

Given a dictionary $D$, your program needs to determine whether several pieces of text are understandable under $D$, and output the position of the longest prefix that is understandable under $D$.

Input

The first line of the input file contains two positive integers $n$ and $m$, representing that there are $n$ words in the dictionary $D$ and $m$ pieces of text to be processed.

The following $n$ lines each describe a word, and the subsequent $m$ lines each describe a piece of text.

Constraints: $1 \le n, m \le 20$, the length of each word does not exceed 10, and the length of each piece of text does not exceed 1M.

Output

For each piece of text provided, you need to output the position of the longest prefix of that text that is understandable under dictionary $D$.

Examples

Input 1

4 3
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

Output 1

14
6
0

Note

The example output corresponds to the following: 14 (the entire text 'whatisyourname' is understandable) 6 (the prefix 'whatis' is understandable) 0 (no prefix is understandable)