← 返回题目列表

Codeforces · 1153/C

C. 薮和括号序列

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

Serval很快就告别了Japari幼儿园,开始了他在Japari小学的生活。

在他最喜欢的数学课上,老师教了他以下有趣的定义。

括号序列是一个字符串,仅包含字符“(”和“)”。

正确的括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。例如,括号序列“()()”、“(())”是正确的(结果表达式是:“(1+1)+(1+1)”、“((1+1)+1)”),而“)(”和“)”则不正确。请注意,根据定义,空字符串是正确的括号序列。

我们将 $$$|s|$$$ 定义为字符串 $$$s$$$ 的长度。字符串 $$$s = s_1s_2\dots s_{|s|}$$$ 的严格前缀 $$$s[1\dots l]$$$ $$$(1\leq l< |s|)$$$ 是字符串 $$$s_1s_2\dots s_l$$$。请注意,根据定义,空字符串和整个字符串不是任何字符串的严格前缀。

学习了这些定义后,他提出了一个新问题。他写下一个字符串$$$s$$$,仅包含字符“(”、“)”和“?”。而他要做的,就是替换掉每一个“?”。在 $$$s$$$ 中独立地通过“(”和“)”之一来使新序列的所有严格前缀都不是正确的括号序列,而新序列应该是正确的括号序列。

毕竟他只是个小学生,这个问题对他来说太难解决了。作为他最好的朋友,你能帮他替换问号吗?如果有多种解决方案,则任何一个都可以接受。

输入

第一行包含一个整数 $$$|s|$$$ ($$$1\leq |s|\leq 3 \cdot 10^5$$$),即字符串的长度。

第二行包含字符串$$$s$$$,仅包含“(”、“)”和“?”。

输出

单行包含代表答案的字符串。

如果有多种解决方案,则任何一个都可以接受。

如果没有答案,则打印包含“:(”(不带引号)的单行。

示例

输入 #1

6
(?????

输出 #1

(()())

输入 #2

10
(???(???(?

输出 #2

:(

注意

可以证明第二个样本无解,所以打印“:(”。