cho.sh

Consonant Fencity

Assign each distinct letter one case so that adjacent consonant pairs of different letters contribute when their cases differ, maximizing that count and breaking ties by the ASCII-smallest result.

Medium7GraphGreedyBit manipulationBrute forceNo attempts yetTime limit3sMemory limit512 MB

Problem

Spoken languages have two kinds of sounds, vowels and consonants. A vowel is produced with an open vocal tract, and a consonant is pronounced with the breath at least partly obstructed. The letters a and o write vowel sounds, while b and p are consonants (bad, pot).

The letter y is a vowel in some words (silly) and a consonant in others (yellow). The letter w is usually a consonant (wet), but in English it produces a vowel sound after another vowel (growth), and in languages such as Welsh it is the only vowel of a word.

In this task y and w count as vowels, so the English alphabet has seven vowels: a, e, i, o, u, w and y. Every other letter is a consonant.

The consonant fencity of a string is the number of positions where two neighbouring letters are both consonants and have different cases (a lowercase letter followed by an uppercase one, or the other way round). The consonant fencity of CoNsoNaNts is 2, the consonant fencity of dEsTrUcTiOn is 3, and the consonant fencity of StRenGtH is 5.

You are given a string of lowercase English letters. Change the case of some letters so that all equal letters end up in the same case (no letter appears in the result both as lowercase and as uppercase) and the consonant fencity of the result is as large as possible.

Several strings can reach that maximum. Print the lexicographically smallest one. The comparison follows ASCII order, so the uppercase letters AA to ZZ all come before every lowercase letter.

Input

The only line contains a non-empty string of lowercase English letters. Its length is at most 1 000 0001\,000\,000.

Output

Print one line: the input string with cases changed so that the consonant fencity is maximal. If several such strings exist, print the lexicographically smallest one.