시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB111100.000%

문제

Ildar is attending a boring online lesson. In order to do something, he transforms strings. Initially, he has a string $s$. Ildar wants to get a string $t$ from the string $s$ in minimum number of steps. In one step he can:

  • Remove a character from any position.
  • Insert any character to any position. I.e. before the first character, between two adjacent characters, or after the last character.
  • Replace character at any position with any other character.

The minimum number of such steps needed to transform string $s$ into string $t$ is also known as edit distance between $s$ and $t$.

Ildar has $n$ favorite strings $w_i$. Consider sequence of strings that would occur during the transformation: $s = x_1$, $x_2$, \dots, $x_{m - 1}$, $x_m = t$. Ildar wants as many of $w_i$ as possible to appear in the set $\{x_1, x_2, \dots, x_m\}$. Help Ildar to find out what is the minimum number of steps needed to transform $s$ to $t$, and what is the maximum number of $w_i$ that can appear during this process, also print these strings.

입력

The first line of input contains the string $s$.

The second line of input contains the string $t$.

The third line contains a single integer $n$ ($0 \le n \le 1\,000$). The following $n$ lines contain strings $w_i$.

All strings consist of lowercase English letters, are non-empty, their lengths don't exceed $10\,000$. The total length of all strings doesn't exceed $10\,000$. All strings are distinct, including $s \neq t$, $s \neq w_i$ and $t \neq w_i$.

출력

Output two integers at the first line of output --- the minimum number of steps, needed to transform $s$ into $t$, and the maximum number of strings $w_i$ that can appear in the process of transformation.

After that, output strings $w_i$ that can appear during the transformation, in the same order they would appear. If there are multiple correct answers, you can output any of them.

예제 입력 1

cat
dog
4
dot
pot
rat
oat

예제 출력 1

3 1
dot

예제 입력 2

longlong
double
3
doublon
longleng
dongle

예제 출력 2

6 2
longleng
dongle

힌트

In the second example one of correct transformations is the following:

"longlong" $\rightarrow$ "longleng" $\rightarrow$ "dongleng" $\rightarrow$ "dongleg" $\rightarrow$ "dongle" $\rightarrow$ "donble" $\rightarrow$ "double"

Ildar's favorite strings are highlighted.