Boring Lesson

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

• Remove a character from any position.
• Insert any character at any position. That is, before the first character, between two adjacent characters, or after the last character.
• Replace the 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 the edit distance between $s$ and $t$.

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

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, and their lengths do not exceed $10\,000$. The total length of all strings does not exceed $10\,000$. All strings are distinct, including $s \neq t$, $s \neq w_i$, and $t \neq w_i$.

On the first line of output, print two integers: the minimum number of steps needed to transform $s$ into $t$, and the maximum number of strings $w_i$ that can appear during the transformation.

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

In the second example, one correct transformation is the following:

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

Ildar's favorite strings are highlighted.