차수 k의 알파 관계

두 문자열 $s$와 $t$에 대하여, 길이가 $k$ 이상인 $s$의 접미사(suffix) 중 $t$의 접두사(prefix)와 일치하는 것이 존재할 때, 그리고 그때에만 "차수 $k$의 알파 관계"가 성립한다고 하며 이를 $s \xrightarrow{\alpha^k} t$로 표기한다. 알파 관계는 $k = 0$일 때는 정의되지 않는다.

예를 들어 "telnet"은 "network"와 $\alpha^3$ 관계이다("telnet"의 접미사 "net"이 "network"의 접두사이다). 또한 "block"은 "locker"와 $\alpha^4$ 관계이다(따라서 $\alpha^3$, $\alpha^2$, $\alpha^1$ 관계이기도 하다. "block"의 접미사 "lock"이 "locker"의 접두사이다).

단어 $s$에서 단어 $t$로 가는 길이 $L$($L > 0$)의 $\alpha^k$ 사슬(chain)이란, 첫 단어가 $s$, 마지막 단어가 $t$이고 인접한 두 단어 사이마다 $\alpha^k$ 관계가 성립하는 $L+1$개의 단어 목록을 뜻한다. 예를 들어 다음은 "cartoon"에서 "manual"로 가는 길이 $4$의 $\alpha^2$ 사슬이다.

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

단어 사전 $C$와 여러 개의 질의가 주어진다. 각 질의는 사전에 속한 두 단어 $s$, $t$와 두 정수 $k$, $L$로 이루어진다. 각 질의에 대하여, $C$의 단어만을 사용하고 길이가 $L$을 넘지 않는 $s$에서 $t$로의 $\alpha^k$ 사슬이 존재하는지 판별하고, 존재한다면 가장 짧은 사슬의 길이를 구하여라.

첫째 줄에 테스트 케이스의 개수 $D$가 주어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $W$와 $Q$가 주어진다. $W$는 이 테스트 케이스의 사전에 있는 단어의 개수, $Q$는 질의의 개수이다. $0 < W < 50000$, $0 < Q < 100$이 보장된다.

이어지는 $W$개의 줄에는 사전의 단어가 한 줄에 하나씩 주어진다. 모든 단어는 소문자 알파벳으로만 이루어지고, 공백을 포함하지 않으며, 길이는 최대 $64$자이고, 같은 단어가 두 번 나오지 않는다.

그 다음 $Q$개의 줄에는 각 질의가 주어진다. 각 줄에는 사전에 속한 두 단어 $s$, $t$와 두 정수 $k$, $L$이 하나의 공백으로 구분되어 주어진다.

각 질의마다 정확히 한 줄을 출력한다.

$a$를 테스트 케이스 번호($1$부터 시작), $b$를 해당 테스트 케이스 안에서의 질의 번호(역시 $1$부터 시작)라고 하자.

사전의 단어만을 사용하고 길이가 $L$ 이하인 $s$에서 $t$로의 $\alpha^k$ 사슬이 존재하지 않으면 다음과 같이 출력한다.

a.b none

존재한다면, 가장 짧은 사슬의 길이(인접한 단어 사이의 단계 수)를 $c$라 할 때 다음과 같이 출력한다.

a.b c

$c$ 값은 유일하게 결정되므로, 각 질의에 대한 정답 출력은 정확히 하나이다.