레벤슈타인 거리

두 문자열의 레벤슈타인 거리는 한 문자열을 다른 문자열로 바꾸는 데 필요한 최소 횟수의 한 글자 단위 연산이다. 연산은 다음과 같다.

• 문자열의 아무 위치에나 글자를 추가한다.
• 문자열의 아무 위치에서나 글자를 제거한다.
• 문자열의 어떤 글자든 다른 글자로 바꾼다.

주어진 알파벳과 질의 문자열이 있을 때, 그 알파벳으로 만들 수 있는 서로 다른 문자열 중 질의 문자열과 레벤슈타인 거리가 1인 것을 모두 찾아 사전순으로 나열하라. 중복은 허용하지 않는다.

질의 문자열 자체는 목록에 포함되지 않는다. 자기 자신과의 레벤슈타인 거리는 1이 아니라 0이다.

입력은 정확히 두 줄이다. 첫째 줄에는 공백 없이 사전순으로 나열된 서로 다른 소문자들이 주어진다. 이것이 사용할 알파벳이다.

둘째 줄에는 문자열 s (2 ≤ |s| ≤ 100)가 주어진다. s는 주어진 알파벳의 소문자로만 이루어져 있다. 이것이 질의 문자열이다.

질의 문자열 $s$와 레벤슈타인 거리가 1인 모든 문자열을 사전순으로 출력하라. 한 줄에 하나씩 출력하며, 중복은 허용하지 않는다.