29514번 - Признание 스페셜 저지다국어

Один очень стеснительный рыцарь решил признаться в своих чистых и высоких чувствах прекрасной принцессе Настеньке. Ввиду своей стеснительности он не может сделать это прямо, поэтому решил написать признание анонимно и отправить его голубиной почтой принцессе. Однако он испугался, что она может догадаться, кто автор признания, и решил притвориться роботом-спамером. Для этого он решил написать признание так, чтобы регистры букв в нем шли в чередующемся порядке.

Принявшись писать признание, рыцарь сильно разволновался, и получилось так, что все буквы в признании написаны в каком попало регистре. Заметив эту оплошность, рыцарь взялся было ее исправлять. Однако это оказалось не так-то просто. Хотя рыцарь и умел делать достаточно аккуратные и незаметные исправления, хотелось все же сделать их как можно меньше, ибо большое число исправлений все-таки бросалось бы в глаза. Это осложнялось тем, что признание вышло очень длинным, и непонятно было, какие же буквы нужно исправить.

Помогите рыцарю справиться с его нелегкой задачей!

Во входном файле дана непустая строка $S$, которая может содержать строчные и заглавные латинские буквы, пробелы и символы <<.>>, <<,>>, <<!>>, <<?>>, <<:>>, <<;>> и <<->>. Строка состоит не более чем из $10^5$ символов.

В выходной файл нужно вывести строку $T$, удовлетворяющую следующим свойствам:

• если $i$-й символ строки $S$ не является буквой, то $i$-й символ строки $T$ совпадает с ним;
• если $i$-й символ строки $S$ является буквой, то $i$-й символ строки $T$ является той же буквой, но, возможно, в другом регистре;
• если между двумя некоторыми буквами строки $T$ нет других букв, то регистр этих букв различен;
• суммарное число позиций, в которых $S$ и $T$ различаются, должно быть минимальным из возможных при условии выполнения предыдущих пунктов.

Если возможных ответов несколько, выведите любой.