암호화 시스템

어떤 프로그래머가 새 암호화 시스템을 만들었다. 그런데 이 시스템에는 서로 다른 두 개 이상의 문자열이 같은 문자열로 암호화되는 결함이 있다.

이 시스템으로 암호화한 문자열이 하나 있다. 원래 문자열을 복원하려면 암호화 전 문자열의 후보를 모두 나열해야 한다. 이 일을 하는 프로그램을 작성하시오.

암호화는 소문자('a'부터 'z')로만 이루어진 문자열에 다음 단계를 순서대로 적용한다.

1. 첫 번째 'b'를 'a'로 바꾼다. 'b'가 없으면 아무것도 하지 않는다.
2. 첫 번째 'c'를 'b'로 바꾼다. 'c'가 없으면 아무것도 하지 않는다.
3. ...
4. 첫 번째 'z'를 'y'로 바꾼다. 'z'가 없으면 아무것도 하지 않는다.

각 단계는 바로 앞 단계가 남긴 문자열에 적용한다. 후보도 소문자로만 이루어진 문자열이다.

입력은 최대 100개의 데이터 집합으로 이루어진다. 각 데이터 집합은 암호화된 문자열 하나가 적힌 한 줄이다. 암호화된 문자열은 소문자로만 이루어지고, 길이는 1 이상 20 이하이다.

입력의 마지막 줄에는 '#' 한 글자만 있다.

각 데이터 집합마다 암호화 전 문자열의 후보 개수 $n$을 한 줄에 먼저 출력하고, 이어서 후보를 한 줄에 하나씩 출력한다. $n$이 10 이하이면 후보를 모두 사전순으로 출력하고, 그렇지 않으면 사전순으로 앞의 다섯 개와 뒤의 다섯 개를 출력한다. $n$이 0이면 0만 출력한다.

여기서 사전순은 다음과 같이 재귀적으로 정의한다. 빈 문자열이 사전순으로 가장 앞에 온다. 비어 있지 않은 두 문자열 $x = x_1 \dots x_k$와 $y = y_1 \dots y_l$에 대해 다음 중 하나가 성립하면 $x$가 $y$보다 사전순으로 앞선다.

• $x_1$이 알파벳 순서('a'부터 'z')에서 $y_1$보다 앞선다.
• $x_1$과 $y_1$이 같은 문자이고, $x_2 \dots x_k$가 $y_2 \dots y_l$보다 사전순으로 앞선다.