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
:(
注意
可以证明第二个样本无解,所以打印“:(”。