자바어 암호 분석

자바어(Javanese)는 인도네시아 자바섬 중부와 동부 사람들이 쓰는 언어이다.

1926년, 자바어를 위해 영어 알파벳을 사용하는 표준 표기법이 만들어졌다. 이 표기법은 A부터 Z까지 26개의 글자를 모두 사용한다. 그중 A, E, I, O, U 다섯 글자는 모음이고, 나머지 21개 글자는 자음이다. 자바어 단어에서는 모음과 자음이 항상 번갈아 나타난다. 즉, 모음 두 개가 붙어 있거나 자음 두 개가 붙어 있는 경우가 절대 없다. 이 성질은 암호화된 자바어 문장을 해독할 때 매우 유용하다.

문장 $s$는 여러 단어로 이루어지며, 각 단어는 대문자 알파벳으로만 이루어진다. 문장 $s$의 모든 단어에서 모음과 자음이 번갈아 나타나면(모음끼리 인접하거나 자음끼리 인접하지 않으면) 그 문장을 올바른(legitimate) 문장이라고 부른다.

문장 $s$에 단순 치환 암호가 적용된다. 즉, 26개 대문자 집합 위의 전단사 함수 $f$를 하나 정하고, $s$의 각 글자 $c$를 $f(c)$로 바꿔 암호문 $t$를 얻는다. $f$가 전단사이므로, 알파벳 26글자 중 정확히 5개가 모음의 상이고 나머지 21개가 자음의 상이다.

암호문 $t$가 주어진다. $t$로 암호화될 수 있는 올바른 문장 $s$가 존재하는지 판단하여라. 가능한 올바른 문장이 여러 개라면, 출력 조건에 정의된 하나의 표준 문장을 출력해야 한다.

입력은 암호문 $t$이다. 단어들이 하나의 공백 또는 줄바꿈으로 구분되어 주어진다. 각 단어는 대문자 알파벳(A–Z)으로만 이루어진다.

입력의 전체 길이는 $100\,000$자를 넘지 않는다.

$t$로 암호화될 수 있는 올바른 문장 $s$가 존재하지 않으면 impossible 한 단어만 출력한다.

그렇지 않으면 해독한 올바른 문장 $s$를 출력하되, $t$와 완전히 같은 배치를 유지한다. 즉, 글자만 바꾸고 모든 공백과 줄바꿈은 위치까지 그대로 둔다. $t$로 암호화되는 올바른 문장이 여러 개일 수 있는데, 그중 사전순으로 가장 앞서는 문장을 출력한다. 두 후보 문장을 앞에서부터 한 글자씩 비교하여, 처음으로 다른 위치에서 더 작은 글자($A < B < \dots < Z$)를 가진 문장이 더 앞선다. $s$의 모든 글자는 대문자이다.