Gardener and the Capybaras (easy version)

题意翻译

有三个只由字符 `a,b` 构成的字符串 $a,b,c$ ，且 $a\le b,c\le b$ 或 $a\ge b,c\ge b$。 将它们拼在一起构成了一个新字符串 $s$。 现在给你 $s$，($3\le |s|\le 100$)，你要复原这三个字符串。 一共有 $T(T\le 500)$ 组测试数据，所有数据中字符串的总长不会超过 500。 ### 输入格式 第一行，一个数 $T$。 接下来的 $T$ 行，每行一个字符串，表示字符串 $s$。 ### 输出格式 对于每组测试数据，输出一行三个字符串，用空格隔开，表示拆出的三个字符串。 如果有多种拆分方式，输出任意一种。 如果无法拆分，则输出 `:(`。 ### 说明/提示 定义字符串 $x$ 小于 $y$ ，当且仅当： $x$ 是 $y$ 的前缀，且 $x \not =y$ 。 或 在 $x$ 与 $y$ 的第一个不同的位置，$x$ 的这一位字符是 `a`，$y$ 的这一位字符是 `b`。

题目描述

This is an easy version of the problem. The difference between the versions is that the string can be longer than in the easy version. You can only do hacks if both versions of the problem are passed. Kazimir Kazimirovich is a Martian gardener. He has a huge orchard of binary balanced apple trees. Recently Casimir decided to get himself three capybaras. The gardener even came up with their names and wrote them down on a piece of paper. The name of each capybara is a non-empty line consisting of letters "a" and "b". Denote the names of the capybaras by the lines $ a $ , $ b $ , and $ c $ . Then Casimir wrote the nonempty lines $ a $ , $ b $ , and $ c $ in a row without spaces. For example, if the capybara's name was "aba", "ab", and "bb", then the string the gardener wrote down would look like "abaabbb". The gardener remembered an interesting property: either the string $ b $ is lexicographically not smaller than the strings $ a $ and $ c $ at the same time, or the string $ b $ is lexicographically not greater than the strings $ a $ and $ c $ at the same time. In other words, either $ a \le b $ and $ c \le b $ are satisfied, or $ b \le a $ and $ b \le c $ are satisfied (or possibly both conditions simultaneously). Here $ \le $ denotes the lexicographic "less than or equal to" for strings. Thus, $ a \le b $ means that the strings must either be equal, or the string $ a $ must stand earlier in the dictionary than the string $ b $ . For a more detailed explanation of this operation, see "Notes" section. Today the gardener looked at his notes and realized that he cannot recover the names because they are written without spaces. He is no longer sure if he can recover the original strings $ a $ , $ b $ , and $ c $ , so he wants to find any triplet of names that satisfy the above property. 

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows. The only line of a test case contains the string $ s $ ( $ 3 \le |s| \le 100 $ ) — the names of the capybaras, written together. The string consists of English letters 'a' and 'b' only. It is guaranteed that the sum of string lengths over all test cases does not exceed $ 500 $ .

输出格式

For each test case, print three strings $ a $ , $ b $ and $ c $ on a single line, separated by spaces — names of capybaras, such that writing them without spaces results in a line $ s $ . Either $ a \le b $ and $ c \le b $ , or $ b \le a $ and $ b \le c $ must be satisfied. If there are several ways to restore the names, print any of them. If the names cannot be recovered, print ":(" (without quotes).

输入输出样例

输入样例 #1

5
bbba
aba
aaa
abba
abbb

输出样例 #1

b bb a
a b a
a a a
ab b a
a bb b

说明

A string $ x $ is lexicographically smaller than a string $ y $ if and only if one of the following holds: - $ x $ is a prefix of $ y $ , but $ x \ne y $ ; - in the first position where $ x $ and $ y $ differ, the string $ x $ has the letter 'a', and the string $ y $ has the letter 'b'. Now let's move on to the examples. In the first test case, one of the possible ways to split the line $ s $ into three lines — "b", "bb", "a". In the third test case, we can see that the split satisfies two conditions at once (i. e., $ a \le b $ , $ c \le b $ , $ b \le a $ , and $ b \le c $ are true simultaneously).