A2. Садовник и капибары (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Различия между версиями заключаются в ограничениях на длину строки. Вы можете делать взломы, только если обе версии задачи сданы.

Казимир Казимирович — марсианский садовник. У него есть огромный сад, в котором растут двоичные сбалансированные яблони.

Недавно Казимир решил завести себе трех капибар. Садовник даже придумал им имена и записал их на листе бумаги. Имя каждой из капибар — непустая строка, состоящая из строчных букв «a» и «b».

Обозначим имена капибар строками $$$a$$$, $$$b$$$ и $$$c$$$. Тогда Казимир записал непустые строки $$$a$$$, $$$b$$$ и $$$c$$$ подряд без пробелов. Например, если капибар звали «aba», «ab» и «bb», то записанная садовником строка будет выглядеть как «abaabbb».

Садовник запомнил интересное свойство: либо строка $$$b$$$ лексикографически не меньше строк $$$a$$$ и $$$c$$$ одновременно, либо строка $$$b$$$ лексикографически не больше строк $$$a$$$ и $$$c$$$ одновременно. Иными словами, либо выполнено $$$a \le b$$$ и $$$c \le b$$$, либо выполнено $$$b \le a$$$ и $$$b \le c$$$ (а возможно, и оба условия одновременно). Здесь $$$\le$$$ обозначает лексикографическое «меньше или равно» для строк. Таким образом, $$$a \le b$$$ значит, что строки должны быть либо равны, либо строка $$$a$$$ должна стоять раньше в словаре, чем строка $$$b$$$. Более подробное объяснение этой операции см. в разделе «Примечание».

Сегодня садовник взглянул на свои записи и понял, что не может восстановить имена, поскольку они записаны без пробелов. Он уже не уверен, сможет ли восстановить оригинальные строки $$$a$$$, $$$b$$$ и $$$c$$$, поэтому ему хочется найти любую тройку имен, которая удовлетворяет описанному выше свойству.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В единственной строке набора входных данных находится строка $$$s$$$ ($$$3 \le |s| \le 2 \cdot 10^5$$$) — имена капибар, записанные слитно. Строка состоит только из латинских букв «a» и «b».

Гарантируется, что сумма длин строк по всем наборам тестовых данных не превосходит $$$4 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите на отдельной строке три строки $$$a$$$, $$$b$$$ и $$$c$$$, разделенные пробелами — имена, при записи которых без пробелов получается строка $$$s$$$. При этом должно выполняться либо $$$a \le b$$$ и $$$c \le b$$$, либо $$$b \le a$$$ и $$$b \le c$$$.

Если способов восстановить имена несколько, то выведите любой из них. Если имена восстановить невозможно, то выведите «:(» (без кавычек).

Пример
Входные данные
5
bbba
aba
aaa
abba
abbb
Выходные данные
b bb a
a b a
a a a
ab b a
a bb b
Примечание

Строка $$$x$$$ лексикографически меньше строки $$$y$$$, если и только если выполняется один из следующих пунктов:

  • $$$x$$$ — префикс $$$y$$$, но $$$x \ne y$$$;
  • в первой позиции, где $$$x$$$ и $$$y$$$ различны, в строке $$$x$$$ находится буква «a», а в строке $$$y$$$ — буква «b».

Теперь перейдем к примерам.

В первом наборе входных данных один из возможных способов разбить строку $$$s$$$ на три строки — это «b», «bb», «a».

В третьем наборе входных данных можно заметить, что разбиение удовлетворяет двум условиям сразу (т. е. $$$a \le b$$$, $$$c \le b$$$, $$$b \le a$$$ и $$$b \le c$$$ верны одновременно).