CF1153C.Serval and Parenthesis Sequence

Serval soon said goodbye to Japari kindergarten, and began his life in Japari Primary School.

In his favorite math class, the teacher taught him the following interesting definitions.

A parenthesis sequence is a string, containing only characters "(" and ")".

A correct parenthesis sequence is a parenthesis sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example, parenthesis sequences "()()", "(())" are correct (the resulting expressions are: "(1+1)+(1+1)", "((1+1)+1)"), while ")(" and ")" are not. Note that the empty string is a correct parenthesis sequence by definition.

We define that $|s|$ as the length of string $s$. A strict prefix $s[1\dots l]$ $(1\leq l \lt |s|)$ of a string $s = s_1s_2\dots s_{|s|}$ is string $s_1s_2\dots s_l$. Note that the empty string and the whole string are not strict prefixes of any string by the definition.

Having learned these definitions, he comes up with a new problem. He writes down a string $s$ containing only characters "(", ")" and "?". And what he is going to do, is to replace each of the "?" in $s$ independently by one of "(" and ")" to make all strict prefixes of the new sequence not a correct parenthesis sequence, while the new sequence should be a correct parenthesis sequence.

After all, he is just a primary school student so this problem is too hard for him to solve. As his best friend, can you help him to replace the question marks? If there are many solutions, any of them is acceptable.

小野猫（Serval）很快告别了加帕里幼儿园，开始了他在加帕里小学的生活。

在他最喜爱的数学课上，老师教给了他以下有趣的定义：

括号序列 是一个仅由字符 "(" 和 ")" 组成的字符串。

合法括号序列 是一种括号序列，它可以通过在原序列的字符之间插入字符 "1" 和 "+"，从而转化为一个合法的算术表达式。例如，括号序列 "()()"、"(())" 是合法的（对应得到的表达式分别为："(1+1)+(1+1)"、"((1+1)+1)"），而 ")(" 和 ")" 则不是。注意：根据定义，空字符串是一个合法括号序列。

我们用 $|s|$ 表示字符串 $s$ 的长度。对于字符串 $s = s_1s_2\dots s_{|s|}$，其严格前缀 $s[1\dots l]$（其中 $1\leq l \lt |s|$）定义为子串 $s_1s_2\dots s_l$。注意：根据定义，空字符串和整个字符串本身均不被视为任何字符串的严格前缀。

在学习了这些定义后，他提出了一个新问题：他写下了一个仅包含字符 "("、")" 和 "?" 的字符串 $s$。他的目标是：将 $s$ 中每个 "?" 独立地 替换为 "(" 或 ")"，使得所得新序列满足两个条件：

• 所有严格前缀均不是合法括号序列；
• 新序列本身是一个合法括号序列。

毕竟，他只是一名小学生，这个问题对他来说太难了。作为他最好的朋友，你能帮他完成问号的替换吗？如果存在多种解法，输出任意一种即可。

The first line contains a single integer $|s|$ ($1\leq |s|\leq 3 \cdot 10^5$), the length of the string.

The second line contains a string $s$, containing only "(", ")" and "?".

第一行包含一个整数 $|s|$（$1\leq |s|\leq 3 \cdot 10^5$），表示字符串的长度。

第二行包含一个字符串 $s$，仅由字符 "("、")" 和 "?" 组成。

A single line contains a string representing the answer.

If there are many solutions, any of them is acceptable.

If there is no answer, print a single line containing ":(" (without the quotes).

一行中包含一个表示答案的字符串。

如果存在多个解，输出任意一个即可。

如果无解，则输出一行“:(”（不含引号）。

It can be proved that there is no solution for the second sample, so print ":(".

可以证明第二个样例无解，因此输出 ":(".