시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 34 6 6 23.077%

문제

주연이는 "Hangman"이라 불리는 게임을 하고 있다. 이 게임의 목표는 감춰진 알파벳을 모두 맞히는 게임이다.

맨 처음에 주연이가 맞춰야 할 단어의 각 알파벳은 '-'로 가려져있다. 그러면 주연이는 알파벳 하나를 고른다. 만약 그 알파벳이 단어에 포함되어 있다면 그 알파벳에 해당하는 모든 단어가 드러난다. 주연이가 모든 알파벳을 맞히면 게임은 끝난다.

주연이는 워낙 고수라 알파벳의 개수만 보고도 단어를 맞출 수 있다. 주연이는 가능한 한 빨리 게임을 끝내고 싶어한다.

단어를 선택하기 위해 주연이는 LEFT, RIGHT, OK라는 3개의 버튼을 사용한다

  • 화면에는 항상 한 개의 알파벳이 보여진다. 맨 처음에 보여지는 알파벳은 'A'이다.
  • "OK" 버튼을 누르면 화면에 나타난 단어를 선택하게 되고, 감춰진 단어에서 이 알파벳과 일치하는 부분이 드러난다. 이 때, 화면에 나타난 단어의 상태는 변하지 않는다.
  • "LEFT" 버튼을 누르면 화면의 알파벳이 이전 것으로 바뀐다. 예를 들어, C는 B로 되고 A는 Z로 된다.
  • "RIGHT" 버튼을 누르면 화면의 알파벳이 다음 것으로 바뀐다. 예를 들어, B는 C가 되고 Z는 A가 된다.

주연이가 버튼을 가장 적게 눌러서 게임을 끝낼 수 있는 방법을 알아내고, 그 방법으로 밝혀내야 할 알파벳의 순서를 출력하시오. (단, 정답이 여러개가 있다면 그 중 아무거나 출력하면 된다.)

입력

첫 줄에 감춰진 단어가 입력으로 들어온다. 단어의 길이는 1 이상이고 100 이하이며, 알파벳 대문자 또는 공백으로 이루어져있다. 또한 단어의 양 끝은 공백이 아니고, 공백은 최대 한 개가 있다.

출력

첫 줄에 게임을 끝내기 위해 버튼을 눌러야 하는 최소 횟수를 출력하시오.

두 번째 줄에는 위의 방법으로 버튼을 눌렀을 때, 알파벳을 밝혀지는 순서대로 출력하시오.

예제 입력

TURBO

예제 출력

19
BUTRO

힌트

예시에서 주연이는 다음의 순서로 버튼을 누르면 된다.

RIGHT, OK, LEFT 7번, OK, LEFT, OK, LEFT 2번, OK, LEFT 3번, OK