Alpha of Degree k

Given two strings $s$ and $t$, we say that the relation "alpha of degree $k$", written $s \xrightarrow{\alpha^k} t$, holds between $s$ and $t$ if and only if there exists a suffix of $s$ of length at least $k$ that is also a prefix of $t$. The alpha relation is not defined for $k = 0$.

For example, "telnet" is $\alpha^3$-related to "network" (the suffix "net" of "telnet" is a prefix of "network"), while "block" is $\alpha^4$-related (and therefore also $\alpha^3$-, $\alpha^2$-, and $\alpha^1$-related) to "locker" (the suffix "lock" of "block" is a prefix of "locker").

An $\alpha^k$ chain of length $L$ (with $L > 0$) from a word $s$ to a word $t$ is a list of $L+1$ words in which $s$ is the first word, $t$ is the last word, and the $\alpha^k$ relation holds between every pair of consecutive words. For example, the following is an $\alpha^2$ chain of length $4$ from "cartoon" to "manual":

$cartoon \xrightarrow{\alpha^2} one \xrightarrow{\alpha^2} new \xrightarrow{\alpha^2} newsman \xrightarrow{\alpha^2} manual$

You are given a dictionary of words $C$ together with several queries. Each query gives two words $s$ and $t$ (both taken from the dictionary) and two integers $k$ and $L$. For each query, decide whether there is an $\alpha^k$ chain from $s$ to $t$ that uses only words from $C$ and whose length does not exceed $L$; if so, report the length of the shortest such chain.

The first line contains a single integer $D$, the number of test cases.

Each test case begins with a line containing two integers $W$ and $Q$, where $W$ is the number of words in this test case's dictionary and $Q$ is the number of queries. It is guaranteed that $0 < W < 50000$ and $0 < Q < 100$.

The next $W$ lines each contain one dictionary word. Every word consists only of lowercase letters, contains no spaces, is at most $64$ characters long, and no word appears more than once.

Each of the following $Q$ lines describes one query: two words $s$ and $t$ (both from the dictionary) and two integers $k$ and $L$, separated by single spaces.

For each query, print exactly one line.

Let $a$ be the test case number (starting from $1$) and let $b$ be the query number within that test case (also starting from $1$).

If there is no $\alpha^k$ chain from $s$ to $t$ that uses only dictionary words and has length at most $L$, print:

a.b none

Otherwise, let $c$ be the length (the number of consecutive-word steps) of the shortest such chain, and print:

a.b c

The value $c$ is uniquely determined, so exactly one output is correct for each query.