← 返回题目列表

Codeforces · 1775/A2

A2. 园丁和水豚(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。版本之间的区别在于字符串可能比简单版本中的字符串更长。只有当问题的两个版本都通过后,你才能进行 hack。

卡齐米尔·卡齐米罗维奇是一名火星园丁。他有一个巨大的果园,里面长满了二元平衡的苹果树。

最近卡西米尔决定给自己养三只水豚。园丁甚至想出了他们的名字并写在一张纸上。每只水豚的名字都是由字母“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$$$ 。

如果有多种方法可以恢复名称,请打印其中任何一种。如果无法恢复名称,请打印“:(”(不带引号)。

示例

输入 #1

5
bbba
aba
aaa
abba
abbb

输出 #1

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$$$ 同时成立)。