자음 대비

사람의 말소리는 모음과 자음으로 나뉜다. 모음은 성도를 열고 내는 소리이고, 자음은 숨이 적어도 일부 막힌 상태에서 발음된다. 예를 들어 a와 o는 모음 소리를 적는 글자이고, b와 p는 자음이다 (bad, pot).

y는 모음으로 쓰이기도 하고 (silly) 자음으로 쓰이기도 한다 (yellow). w는 보통 자음이지만 (wet) 영어에서 다른 모음 뒤에 오면 모음 소리를 내고 (growth), 웨일스어처럼 한 단어의 유일한 모음이 되는 언어도 있다.

이 문제에서는 y와 w를 모음으로 본다. 따라서 영어 알파벳의 모음은 a, e, i, o, u, w, y 일곱 개이고 나머지 글자는 모두 자음이다.

문자열의 자음 대비(consonant fencity)는 이웃한 두 글자가 모두 자음이면서 대소문자가 서로 다른 (소문자 뒤에 대문자가 오거나 그 반대인) 위치의 개수다. 예를 들어 CoNsoNaNts의 자음 대비는 2, dEsTrUcTiOn의 자음 대비는 3, StRenGtH의 자음 대비는 5이다.

소문자 영어 알파벳으로만 이루어진 문자열이 주어진다. 일부 글자의 대소문자를 바꿔서 같은 글자는 모두 같은 대소문자가 되게 하고 (즉 결과 문자열에서 어떤 글자도 대문자와 소문자로 동시에 나타나지 않는다), 결과 문자열의 자음 대비를 최대로 만들어라.

자음 대비가 최대인 문자열이 여럿이면 그중 사전순으로 가장 앞선 것을 출력한다. 비교는 아스키 코드 순서를 따르므로 대문자 $A$부터 $Z$까지는 모든 소문자보다 앞선다.

첫째 줄에 소문자 영어 알파벳으로 이루어진, 비어 있지 않은 문자열이 주어진다. 길이는 $1\,000\,000$ 이하다.

첫째 줄에 자음 대비가 최대가 되도록 대소문자를 바꾼 문자열을 출력한다. 그런 문자열이 여럿이면 사전순으로 가장 앞선 것을 출력한다.