Understanding Punctuation-less Text

A text T is a string of lowercase letters without any punctuation. A word W is also a string of lowercase letters. A dictionary D is a collection of words. A text T is said to be understandable under the dictionary D if it can be segmented into one or more parts such that every part is a word in D.

For example, let D contain the words is, name, what, and your. Then the text whatisyourname is understandable under D since it can be segmented as what, is, your, name, all belonging to D. In contrast, the text whatisyouname is not understandable under D (but would be if the word you were added to D). In addition, whatis is the longest prefix of whatisyouname that is understandable under D.

Your task is: given a dictionary D and several texts, determine for each text whether it is fully understandable under D and also output the length of the longest prefix that is understandable under D.

Mathematically, let the text be represented as a string $T$ of lowercase letters of length $n$. Define a boolean array $\textit{dp}$ such that $\textit{dp}[0]=true$ and for $1 \le i \le n$, $\textit{dp}[i] = true$ if there exists a $j$ with $0 \le j < i$ for which $\textit{dp}[j]$ is true and the substring $T[j:i]$ is in D. The text is fully understandable if $\textit{dp}[n]$ is true, and the longest understandable prefix is the maximum index $i$ for which $\textit{dp}[i]$ is true.

Note: All formulas are written in LaTeX format.

inputFormat

The input begins with an integer N, the number of words in the dictionary.

Then follow N lines, each containing a dictionary word.

Next, there is an integer M which denotes the number of texts.

Then follow M lines, each containing a text composed only of lowercase letters.

outputFormat

For each text, output two integers separated by a single space on one line. The first integer should be 1 if the entire text is understandable under the given dictionary or 0 otherwise. The second integer is the length of the longest prefix of the text that is understandable under the dictionary.

sample

4
is
name
what
your
2
whatisyourname
whatisyouname

1 14
0 6