지루한 수업

Ildar는 지루한 온라인 수업을 듣고 있다. 심심함을 달래려고 그는 문자열을 변형한다. 처음에 그는 문자열 $s$를 가지고 있다. Ildar는 문자열 $s$에서 문자열 $t$를 최소 횟수의 단계로 얻고 싶어 한다. 한 단계에서 그는 다음을 할 수 있다:

• 임의의 위치에서 문자를 제거한다.
• 임의의 위치에 임의의 문자를 삽입한다. 즉 첫 번째 문자 앞, 인접한 두 문자 사이, 또는 마지막 문자 뒤에 삽입한다.
• 임의의 위치에 있는 문자를 다른 임의의 문자로 바꾼다.

문자열 $s$를 문자열 $t$로 변환하는 데 필요한 이러한 단계의 최소 횟수는 $s$와 $t$ 사이의 편집 거리라고도 한다.

Ildar에게는 $n$개의 좋아하는 문자열 $w_i$가 있다. 변환이 진행되는 동안 나타나는 문자열의 나열 $s = x_1$, $x_2$, \dots, $x_{m - 1}$, $x_m = t$를 생각하자. Ildar는 $w_i$ 중 가능한 한 많은 문자열이 집합 $\{x_1, x_2, \dots, x_m\}$에 나타나기를 원한다. Ildar가 $s$를 $t$로 변환하는 데 필요한 최소 단계 수와, 이 과정에서 나타날 수 있는 $w_i$의 최대 개수를 구하고, 해당 문자열들도 출력하도록 도와라.

입력의 첫 번째 줄에는 문자열 $s$가 주어진다.

입력의 두 번째 줄에는 문자열 $t$가 주어진다.

세 번째 줄에는 정수 $n$이 하나 주어진다 ($0 \le n \le 1\,000$). 다음 $n$개의 줄에는 문자열 $w_i$가 주어진다.

모든 문자열은 소문자 영어 알파벳으로 이루어져 있고, 비어 있지 않으며, 길이는 $10\,000$을 넘지 않는다. 모든 문자열의 길이의 합은 $10\,000$을 넘지 않는다. 모든 문자열은 서로 다르며, $s \neq t$, $s \neq w_i$, $t \neq w_i$이다.

출력의 첫 번째 줄에는 $s$를 $t$로 변환하는 데 필요한 최소 단계 수와, 변환 과정에서 나타날 수 있는 문자열 $w_i$의 최대 개수를 출력한다.

그다음에는 변환 과정에서 나타날 수 있는 문자열 $w_i$를, 나타나는 순서대로 출력한다. 정답이 여러 개라면 그중 아무거나 출력해도 된다.

두 번째 예시에서 올바른 변환 중 하나는 다음과 같다:

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

Ildar가 좋아하는 문자열은 굵게 표시했다.