← 返回题目列表

Codeforces · 1146/B

B. 讨厌“A”

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

Bob 有一个由小写英文字母组成的字符串 $$$s$$$。他将 $$$s'$$$ 定义为从 $$$s$$$ 中删除所有“a”字符(保持所有其他字符按相同顺序)后的字符串。然后,他通过连接 $$$s$$$ 和 $$$s'$$$ 生成一个新字符串 $$$t$$$。换句话说,$$$t=s+s'$$$(参见注释中的示例)。

给你一个字符串 $$$t$$$。你的任务是找到鲍勃可以用来生成$$$t$$$的一些$$$s$$$。可以证明,如果答案存在,它将是唯一的。

输入

输入的第一行包含一个由小写英文字母组成的字符串 $$$t$$$ ($$$1 \leq |t| \leq 10^5$$$)。

输出

打印可能生成 $$$t$$$ 的字符串 $$$s$$$。可以证明答案是否存在,它是唯一的。如果不存在字符串,则打印“:(”(不带双引号,字符之间没有空格)。

示例

输入 #1

aaaaa

输出 #1

aaaaa

输入 #2

aacaababc

输出 #2

:(

输入 #3

ababacacbbcc

输出 #3

ababacac

输入#4

baba

输出#4

:(

注意

在第一个示例中,我们有 $$$s = $$$ "aaaaa",并且 $$$s' = $$$ ""。

在第二个示例中,没有这样的 $$$s$$$ 可以生成给定的 $$$t$$$。

在第三个示例中,我们有 $$$s = $$$ "ababacac",$$$s' = $$$ "bbcc",以及 $$$t = s + s' = $$$ "ababacacbbcc"。