Это сложная версия задачи. Различия между версиями заключаются в ограничениях на длину строки. Вы можете делать взломы, только если обе версии задачи сданы.
Казимир Казимирович — марсианский садовник. У него есть огромный сад, в котором растут двоичные сбалансированные яблони.
Недавно Казимир решил завести себе трех капибар. Садовник даже придумал им имена и записал их на листе бумаги. Имя каждой из капибар — непустая строка, состоящая из строчных букв «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\), поэтому ему хочется найти любую тройку имен, которая удовлетворяет описанному выше свойству.
Выходные данные
Для каждого набора входных данных выведите на отдельной строке три строки \(a\), \(b\) и \(c\), разделенные пробелами — имена, при записи которых без пробелов получается строка \(s\). При этом должно выполняться либо \(a \le b\) и \(c \le b\), либо \(b \le a\) и \(b \le c\).
Если способов восстановить имена несколько, то выведите любой из них. Если имена восстановить невозможно, то выведите «:(» (без кавычек).
Примечание
Строка \(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\) верны одновременно).