CF1775A2.Gardener and the Capybaras (hard version)

This is an hard 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.

这是一个该问题的困难版本。两个版本的区别在于，本版本中的字符串长度可能比简单版本更长。只有当两个版本的问题均通过后，才允许进行 Hack。

卡齐米尔·卡齐米罗维奇是一位火星园丁，他拥有一大片二叉平衡苹果树果园。

最近，卡西米尔决定为自己养三只水豚。这位园丁甚至为它们取好了名字，并将名字写在了一张纸上。每只水豚的名字均为一个非空字符串，仅由字母 “a” 和 “b” 构成。

记这三只水豚的名字分别为字符串 $a$、$b$ 和 $c$。随后，卡西米尔将这三个非空字符串 $a$、$b$、$c$ 按顺序拼接（中间不加空格）写成一个字符串。例如，若三只水豚的名字分别为 "aba"、"ab" 和 "bb"，则园丁所写的字符串即为 "abaabbb"。

园丁记得一个有趣的性质：字符串 $b$ 要么字典序不小于 $a$ 和 $c$（即同时满足 $a \le b$ 与 $c \le b$），要么字典序不大于 $a$ 和 $c$（即同时满足 $b \le a$ 与 $b \le c$）；当然，两种情况也可能同时成立。此处 $\le$ 表示字符串的字典序“小于或等于”关系。也就是说，$a \le b$ 意味着两字符串要么完全相等，要么在字典序中 $a$ 排在 $b$ 之前。关于该运算的更详细说明，请参见“注释”部分。

今天，园丁查看自己的笔记时，发现由于名字之间未加空格，他已无法还原出原始的三个名字。他现在甚至不确定是否还能唯一恢复出原始字符串 $a$、$b$ 和 $c$，因此他希望找出任意一组满足上述性质的三元组 $(a, b, c)$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line of a test case contains the string $s$ ($3 \le |s| \le 2 \cdot 10^5$) — 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 $4 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含字符串 $s$（$3 \le |s| \le 2 \cdot 10^5$）——即水豚的名字连写而成的字符串。该字符串仅由英文字母 'a' 和 'b' 组成。

保证所有测试用例的字符串长度之和不超过 $4 \cdot 10^5$。

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).

对于每个测试用例，在一行中输出三个字符串 $a$、$b$ 和 $c$，以空格分隔——即水豚的名字，使得将它们不加空格拼接后得到字符串 $s$。必须满足以下条件之一：

• $a \le b$ 且 $c \le b$，或
• $b \le a$ 且 $b \le c$。

若存在多种恢复名字的方式，输出任意一种即可。若无法恢复名字，则输出 :(（不带引号）。

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 —is "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).

字符串 $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$ 同时成立）。