| The 2026 ICPC Belarus Qualification |
|---|
| Закончено |
Светозар часто общается со своими друзьями в мессенджерах. Он не любит опечатки и поэтому решил очищать от них сообщения, которые похожи на смех.
Смех — это непустая строка нечётной длины, в которой чередуются одна фиксированная гласная буква и одна фиксированная согласная буква. Иначе говоря, смех имеет один из двух видов:
Здесь $$$v$$$ — некоторая гласная буква, $$$c$$$ — некоторая согласная буква; обе буквы одни и те же на весь смех. В частности, любая одна буква является смехом. Гласными считаются буквы 'a', 'e', 'i', 'o', 'u'. Все остальные строчные латинские буквы считаются согласными (в том числе буква 'y').
Помогите Светозару с реализацией: для заданной строки $$$s$$$ из строчных латинских букв найдите самую длинную её подпоследовательность, являющуюся смехом. Если таких подпоследовательностей несколько, выведите лексикографически наименьшую.
Первая строка содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 2 \cdot 10^5$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.
Единственная строка описания содержит строку $$$s$$$ ($$$1 \leqslant |s| \leqslant 2 \cdot 10^5$$$) из строчных латинских букв.
Гарантируется, что сумма длин строк $$$s$$$ в одном входном файле не превосходит $$$2 \cdot 10^5$$$.
Для каждого тестового случая выведите одну строку — искомую подпоследовательность. Если подходящих подпоследовательностей максимальной длины несколько, выведите лексикографически наименьшую из них.
7ahahahhahhaajajhazaababayayoklolkek
ahahahahahaaaabayaykkek
В примере в первом тестовом случае подходит подпоследовательность ahahahahaha. В третьем тестовом случае строка ab имеет чётную длину и не является смехом, поэтому ответ — буква 'a'. В пятом тестовом случае буква 'y' согласная, и вся строка yay является смехом.
Напомним, что подпоследовательность получается из строки удалением нуля или более символов без изменения порядка оставшихся. Последовательность $$$x$$$ лексикографически меньше последовательности $$$y$$$, если выполняется одно из двух условий:
| Название |
|---|


