Codeforces Round 843 (Div. 2) |
---|
Закончено |
Это сложная версия задачи. Различия между версиями заключаются в ограничениях на длину строки. Вы можете делать взломы, только если обе версии задачи сданы.
Казимир Казимирович — марсианский садовник. У него есть огромный сад, в котором растут двоичные сбалансированные яблони.
Недавно Казимир решил завести себе трех капибар. Садовник даже придумал им имена и записал их на листе бумаги. Имя каждой из капибар — непустая строка, состоящая из строчных букв «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$$$.
Если способов восстановить имена несколько, то выведите любой из них. Если имена восстановить невозможно, то выведите «:(» (без кавычек).
5bbbaabaaaaabbaabbb
b bb a a b a a a a ab b a a bb b
Строка $$$x$$$ лексикографически меньше строки $$$y$$$, если и только если выполняется один из следующих пунктов:
Теперь перейдем к примерам.
В первом наборе входных данных один из возможных способов разбить строку $$$s$$$ на три строки — это «b», «bb», «a».
В третьем наборе входных данных можно заметить, что разбиение удовлетворяет двум условиям сразу (т. е. $$$a \le b$$$, $$$c \le b$$$, $$$b \le a$$$ и $$$b \le c$$$ верны одновременно).
Название |
---|