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


-----Input-----

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 "?".


-----Output-----

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


-----Examples-----
Input
6
(?????

Output
(()())
Input
10
(???(???(?

Output
:(



-----Note-----

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

Difficulty: interview

Starter code:

Solutions:
n = q = int(input())
k = list(input())
cntl = k.count('(')
cntr = k.count(')')
cntq = k.count('?')
for i in range(n):
    if k[i] == '?':
        if cntl < q // 2 and cntr + cntq >= q // 2:
            k[i] = '('
            cntl += 1
            cntq -= 1
        else:
            k[i] = ')'
            cntr += 1
            cntq -= 1
        
def check():
    cnt = 0
    m = 0
    for i in k:
        m += 1
        if i == '(':
            cnt += 1
        else:
            cnt -= 1
        if cnt == 0 and m < n or cnt < 0:
            return False
    return cnt == 0

print(''.join(k) if check() else ':(')
            
            


def main():
    n = int(input())
    arr = list(input())
    if n & 1:
        print(":(")
        return 0
    left = n // 2 - arr.count('(')
    for i in range(n):
        if arr[i] == '?':
            if left:
                arr[i] = '('
                left -=  1
            else:
                arr[i] = ')'
    if arr[0] == ')' or arr[-1] == '(':
        print(":(")
        return 0
    left = 1
    right = 0
    for i in range(1, n):
        if right == left:
            print(":(")
            return 0
        if arr[i] == '(':
            left += 1
        else:
            right += 1
    if left != right:
        print(":(")
        return 0
    print("".join(arr))
    return 0
main()

n = int(input())
if n%2:
    print (":(")
    return
s = [c for c in input()]
if s[0] == ")" or s[-1] == "(":
    print (":(")
    return
s[0] = "("
s[-1] = ")"

count_open = s.count("(")
count_close = s.count(")")
half = n//2
if count_close>half or count_open>half:
    print (":(")
    return
available = half-count_open
current = 0
for i,x in enumerate(s):
    if x == "(":
        current += 1
    elif x == ")":
        current -= 1
    else:
        if available:
            current+=1
            available-=1
            s[i] = "("
        else:
            current -= 1
            s[i] = ")"
    if current == 0 and i!=n-1:
        print (":(")
        return

print ("".join(s))

# AC
import sys


class Main:
    def __init__(self):
        self.buff = None
        self.index = 0

    def __next__(self):
        if self.buff is None or self.index == len(self.buff):
            self.buff = sys.stdin.readline().split()
            self.index = 0
        val = self.buff[self.index]
        self.index += 1
        return val

    def next_int(self):
        return int(next(self))

    def cal(self, s):
        if len(s) == 1:
            return s[0]
        if s[0] == 0:
            return self.cal(s[1:])
        v = 1
        for c in s:
            v *= c
        return v

    def solve(self):
        n = self.next_int()
        s = [x for x in next(self)]
        w = s.count('?')
        z = s.count('(')
        y = n - w - z
        ss = [x for x in s]
        if ss[0] == '?':
            ss[0] = '('
            z += 1
        if ss[-1] == '?':
            ss[-1] = ')'
            y += 1
        flag = (n % 2 == 0 and ss[0] != ')' and ss[-1] != '(' and z * 2 <= n and y * 2 <= n)

        c = 1
        for i in range(1, n - 1):
            if not flag:
                break
            if ss[i] == '(':
                c += 1
            elif ss[i] == ')':
                c -= 1
            elif z * 2 < n:
                ss[i] = '('
                c += 1
                z += 1
            else:
                ss[i] = ')'
                c -= 1
                y -= 1

            if c == 0:
                flag = False

        if not flag:
            print(':(')
        else:
            print(''.join(ss))


def __starting_point():
    Main().solve()

__starting_point()

import sys
# import math

# sys.stdin = open('c-test.txt')

def check(s):
	status = 0
	for char in s[:-1]:
		if char == '(':
			status += 1
		else:
			status -= 1
		if status <= 0:
			return ':('
	return s

n = int(input())
s = input()
if n % 2 != 0:
	print(':(')
else:
	leftcount = 0
	rightcount = 0
	for char in s:
		if char == '(':
			leftcount += 1
		if char == ')':
			rightcount += 1
	needed = n // 2
	if max(leftcount,rightcount) > needed:
		print(':(')
	else:
		leftneeded = (n // 2) - leftcount
		leftadded = 0
		newchars = []
		for char in s:
			if char == '?':
				if leftadded < leftneeded:
					newchars.append('(')
					leftadded += 1
				else:
					newchars.append(')')
			else:
				newchars.append(char)
		print(check(''.join(newchars)))

import sys
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
ans = []
count = 0
for i in s:
    if i == "(":
        ans.append(1)
    elif i == ")":
        ans.append(-1)
    else:
        ans.append(0)
        count +=1
x = sum(ans)
if abs(x) > count or  x%2 != count%2:
    print(":(")
    return
hi = (x + count)//2
mi = count - hi
for i in range(n):
    if ans[i] == 0 and mi:
        ans[i] = 1
        mi-=1
    elif ans[i] == 0:
        ans[i] = -1
rui = [0]*(n+1)
for i in range(n):
    rui[i+1] = rui[i]+ans[i]
    if rui[i+1] <= 0 and i != n-1:
        print(":(")
        return
    if ans[i] == 1:
        ans[i] = "("
    else:
        ans[i] = ")"
print("".join(ans))

n = int(input())
s = list(input())
if n % 2 == 1:
    print(":(")
else:
    op = n // 2 - s.count("(")
    for i in range(n):
        if s[i] == "?":
            if op > 0:
                s[i] = "("
            else:
                s[i] = ")"
            op -= 1
    #print("".join(s))
    b = 0
    for i in range(n):
        if s[i] == ")":
            b -= 1
        else:
            b += 1
        if i != n - 1 and b <= 0:
            print(":(")
            break
    else:
        if b == 0:
            print("".join(s))
        else:
            print(":(")


n = int(input())
s = list(input())
def findbal(a, th=0):
    b = 0
    for c in a:
        if c == '(':
            b += 1
        elif c == ')':
            b -= 1
            if th > 0 and b < th:
                return b
    return b

can = s[ 0 ] != ')' and s[ -1 ] != '(' and (n%2) == 0
if can:
    s[ 0 ] = '('
    s[ -1 ] = ')'
    b = findbal(s)
    q = sum([1 if c == '?' else 0 for c in s])
    q -= b
    q = q // 2
    if q < 0:
        can = False
    for i in range( n ):
        if s[ i ] == '?':
            s[ i ] = '(' if q > 0 else ')'
            q -= 1
    can = findbal(s[:-1], 1) == 1

if can:
    print("".join(s))
else:
    print(":(")


import sys
input = sys.stdin.readline

n=int(input())
s=list(input().strip())

if n%2==1:
    print(":(")
    return

if n==2:
    if s[0]==")" or s[1]=="(":
        print(":(")
        return

    else:
        print("()")
        return

if s[0]==")" or s[1]==")" or s[-1]=="(" or s[-2]=="(":
    print(":(")
    return

s[0]="("
s[1]="("
s[-1]=")"
s[-2]=")"

r=s.count("(")
l=s.count(")")
q=s.count("?")

x=(l-r+q)//2
y=(r-l+q)//2

if x<0 or y<0:
    print(":(")
    return
    
count=0
for i in range(n):
    if s[i]=="?":
        s[i]="("
        count+=1

    if count==x:
        break

for j in range(i,n):
    if s[j]=="?":
        s[j]=")"


NOW=1
for i in range(1,n-1):
    if s[i]=="(":
        NOW+=1
    else:
        NOW-=1

    if NOW==0:
        print(":(")
        return

print("".join(s))

        


n = int(input())
if n % 2:
    print(':(')
    return
s = list(input())
ans = ''
c1, c2 = s.count('('), s.count(')')
cnt90 = 0
cnt9, cnt0 = 0, 0
for i in s[:-1]:
    if i == '(':
        cnt90 += 1
        if cnt9 + cnt90 > n // 2:
            print(':(')
            return
        ans += i
    elif i == ')':
        cnt0 += 1
        if cnt0 > n // 2:
            print(':(')
            return
        ans += i
    else:
        if cnt9 + c1 < n // 2:
            ans += '('
            cnt9 += 1
        else:
            ans += ')'
            cnt0 += 1
    if cnt90 + cnt9 <= cnt0:
        print(':(')
        return
if s[-1] == '(' or cnt9 + cnt90 != n // 2:
    print(':(')
    return
print(ans + ')')

input()
s = input()
if len(s) & 1:
    print(':(')
    raise SystemExit(0)
max_open, min_open = 0, 0
started = False

q_mark = 0
op = 0
cl= 0
ended = False

for c in s:
    if ended:
        print(':(')
        raise SystemExit(0)
    if min_open <= 0 and started:
        min_open = 1
    started = True
    if c == '(':
        op += 1
        max_open += 1
        min_open += 1
    elif c == ')':
        cl += 1
        max_open -= 1
        min_open -= 1
    else:
        q_mark += 1
        max_open += 1
        min_open -= 1
    if max_open < 1:
        ended = True

if min_open != 0:
    print(':(')
    raise SystemExit(0)

s = list(s)
open_count = len(s) // 2 - op
for i in range(len(s)):
    if s[i] == '(':
        op -= 1
    elif s[i] == ')':
        cl -= 1
    elif s[i] == '?':
        if open_count == 0:
            s[i] = ')'
        else:
            s[i] = '('
            open_count -= 1
print(''.join(s))


n = int(input())
l = list(input())

if n % 2 == 1:
    print(':(')
    return

if n == 2:
    if l[0] == ')' or l[1] == '(':
        print(':(')
    else:
        print('()')
    return

if l[0] == ')' or l[1] == ')' or l[-1] == '(' or l[-2] == '(':
    print(':(')
    return

l[0] = '('
l[1] = '('
l[-1] = ')'
l[-2] = ')'

p = l.count(')') - l.count('(')
q = l.count('?')

a = (q + p) // 2
b = q - a

cnt = 0
for i in range(len(l)):
    if l[i] == '?':
        if cnt < a:
            l[i] = '('
        else:
            l[i] = ')'
        cnt += 1

cnt = 0
for p,i in enumerate(l):
    if i == '(':
        cnt += 1
    else:
        cnt -= 1
    if cnt == 0 and p != n - 1:
        print(':(')
        return
else:
    if cnt != 0:
        print(':(')
        return

print(''.join(l))


from itertools import accumulate
N = int(input())
S = input()
if S[0] == ')' or S[-1] == '(' or N % 2 == 1:
    print(':(')
    return
L = [0]*N
posi = 0
nega = 0
for i, s in enumerate(S):
    if s == '(':
        posi += 1
        L[i] = 1
        continue
    elif s == ')':
        nega += 1
        L[i] = -1
        continue
rem = N - posi - nega
sp = nega - posi
pi = (rem + sp)//2
ni = (rem - sp)//2
if pi < 0 or ni < 0:
    print(':(')
    return
LP = L.copy()
for i, a in enumerate(L):
    if not a:
        if pi > 0:
            pi -= 1
            LP[i] = 1
        else:
            LP[i] = -1
if all([i > 0 for i in list(accumulate(LP))[:-1]]):
    print(''.join([('', '(', ')')[l] for l in LP]))
    return
print(':(')

n = int(input())
s = list(input())
if n % 2:
    print(':(')
    return
left = s.count('(')
right = s.count(')')
plus = 0
for i in range(n):
    if s[i] == '?':
        if left < n // 2:
            s[i] = '('
            left += 1
        else:
            s[i] = ')'
            right += 1
    if s[i] == '(':
        plus += 1
    else:
        plus -= 1
    if i != n - 1 and plus <= 0:
        print(':(')
        return
if left == n // 2 and right == n // 2:
    print(''.join(s))
else:
    print(':(')


def fix(S):
    N = len(S)
    s=0
    minS=0
    for n in range(N):
        if S[n] == '(':
            s += 1
        elif S[n] == ')':
            s -= 1
        minS = min(minS, s)
    if minS < 0:
        for n in range(N):
            if S[n] == '?':
                S[n] = '('
                minS += 1
                s += 1
                if not minS: break
    if s > 0:
        for n in range(N-1,-1,-1):
            if S[n] == '?':
                S[n] = ')'
                s -= 1
                if not s: break
    nq = 0
    for n in range(N):
        if S[n] == '?': nq += 1
    if nq % 2: return False
    added = 0
    for n in range(N):
        if S[n] == '?':
            if added < nq//2:
                S[n] = '('
            else:
                S[n] = ')'
            added += 1
    s=0
    for n in range(N):
        if S[n] == '(':
            s += 1
        else:
            s -= 1
        if s < 0: return False
    if s: return False
    return S

def sv():
    N = int(input())
    S = list(input())
    if N%2: return False
    if S[0] == ')' or S[N-1] == '(': return False
    if N == 2:
        print('()')
        return True
    f = fix(S[1:-1])
    if not f: return False
    print('(%s)' % ''.join(f))
    return True

if not sv():
    print(':(')


n=int(input().strip())
ss=input().strip()
q=0
for k in range(n):
    if(ss[k]=="("):
        q+=1
ii=(n//2)-q
count=0
s=""
if(n%2!=0):
    print(":(")
elif(ii<0):
    print(":(")
else:
 for k in range(n):
    if(ss[k]=="?" and count<ii):
        s=s+"("
        count+=1
    elif(ss[k]=="?" and count>=ii):
        s=s+")"
    elif(ss[k]=="("):
        s=s+"("
    else:
        s=s+")"
 c2=0
 c3=0
 for  k in range(n-1):
     if s[k]=="(":
       c2+=1
     else:
       c3+=1
     if(c3>=c2):
         print(":(")
         break
 else:
     if s[n-1]=="(":
       c2+=1
     else:
       c3+=1
     if(c2!=c3):
         print(":(")
     else:
         print(s)

n = int(input())
s = list(input())
l, r = s.count('('), s.count(')')
for i in range(n):
	if s[i] == '?':
		if l + l < n:
			s[i] = '('
			l += 1
		else:
			s[i] = ')'
cnt = 0
for i in range(n):
	cnt += 1 if s[i] == '(' else -1
	if cnt < 1 and i < n - 1:
		print(':(')
		return
	elif cnt != 0 and i == n - 1:
		print(':(')
		return
print(''.join(s))

from collections import Counter
n = int(input())
s = input()
c = Counter(s)
if n & 1 or c['('] > (n // 2) or c[')'] > (n // 2):
    print(":(")
else:
    f1 = n // 2 - c['(']
    f2 = n // 2 - c[')']
    r = []
    for v in s:
        if v == "?":
            if f1 > 0:
                r.append("(")
                f1 -= 1
            else:    
                r.append(")")
                f2 -= 1
        else:
            r.append(v)
    cnt = 0        
    for i, v in enumerate(r):
        if v == "(":
            cnt += 1
        else:    
            cnt -= 1
        if i < n-1 and cnt <= 0:
            print(":(")
            break
    else:
        print("".join(r))



import io, sys, atexit, os

import math as ma
from decimal import Decimal as dec
from itertools import permutations


def li ():
	return list (map (int, input ().split ()))


def num ():
	return map (int, input ().split ())


def nu ():
	return int (input ())


def find_gcd ( x, y ):
	while (y):
		x, y = y, x % y
	return x


mm = 1000000007



def solve ():
	t = 1
	for it in range (t):
		n=nu()
		s=list(input())
		if(n%2==1):
			print(":(")
		else:
			gg=0
			for i in range(n):
				if(s[i]=="("):
					gg+=1
			if(gg>n//2):
				print(":(")
				continue
			dd=n//2-gg
			for i in range(n):
				if(s[i]=="?"):
					if(dd>0):
						s[i]="("
						dd-=1
					else:
						s[i]=")"
			xc=[0]*n
			ss=0
			for i in range(n):
				if(s[i]=="("):
					ss+=1
				else:
					ss-=1
				xc[i]=ss
			fl=True
			for i in range(n-1):
				if(xc[i]<=0):
					fl=False
			if(xc[n-1]!=0):
				fl=False
			if(fl):
				for i in range(n):
					print(s[i],end="")
				print()
			else:
				print(":(")

def __starting_point():
	solve ()
__starting_point()

import sys

def main():
	n = int(input())
	
	s = list(sys.stdin.readline())
	f, ouv = 0, 0
	
	for i in range(n):
		if s[i] == '?' or s[i] == '(':
			ouv += 1
		else:
			f +=1
			ouv -= 1
		#print(i, f, ouv, file = sys.stderr)
		if i < n-1 and ouv <= 0:
			print(':(')
			return

	f, ouv = 0, 0

	for i in range(n):
		if s[n-1-i] == '?' or s[n-1-i] == ')':
			f += 1
		else:
			ouv +=1
			f -= 1
		#print(n-1-i, f, ouv, file = sys.stderr)
		if i < n-1 and f <= 0:
			print(':(')
			return

	if n%2 == 1:
		print(':(')
		return

	k = n//2 - ouv

	for i in range(n):
		if s[i] == '?' and k != 0:
			s[i] = '('
			k-=1
		elif s[i] == '?':
			s[i] = ')'

	print(*s, sep='')

main()

length=int(input())
string=input()
LeftParens=0
questionMarks=0
imposs=False
moreLeftAndQ=0
moreRightAndQBack=0
if length % 2 == 1:
    imposs=True
for i in range(length-1):
    if string[i]=="(":
        LeftParens+=1
        moreLeftAndQ+=1
    elif string[i]==")":
        moreLeftAndQ-=1
        if moreLeftAndQ<1:
            imposs=True
            break
    else:
        moreLeftAndQ+=1
    if string[length-i-1]=="(":
        moreRightAndQBack-=1
        if moreRightAndQBack<1:
            imposs=True
            break
    elif string[length-i-1]==")":
        moreRightAndQBack+=1
    else:
        moreRightAndQBack+=1
        
if imposs:
    print(":(")
else:
    newString=""
    for i in range(length):
            if string[i]=="?":
                if (length/2)-LeftParens>0:
                    newString=newString+"("
                    LeftParens+=1
                else:
                    newString=newString+")"
            else:
                newString=newString+string[i]
    print(newString)

# -*- coding: utf-8 -*-
# @Time    : 2019/4/13 22:44
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : C. Serval and Parenthesis Sequence.py


def main():
    n = int(input())
    s = list(input())

    temp_count = 0
    for c in s:
        if c == '(':
            temp_count += 1

    stack = []
    for i in range(n):
        if i == n - 1 and (len(stack) != 1 or s[i] == '('):
            print(':(')
            return

        if s[i] == '(':
            stack.append(s[i])
        elif s[i] == ')':
            if not stack:
                print(':(')
                return
            stack.pop()
        else:
            if i != n - 1 and temp_count < n // 2:
                s[i] = '('
                stack.append('(')
                temp_count += 1
            else:
                s[i] = ')'
                stack.pop()

        if i != n - 1 and not stack:
            print(':(')
            return
        # print(s)

    print(''.join(s))


def __starting_point():
    main()

__starting_point()

import string, copy


def solution(s):
    if len(s) == 0:
        return ''
    if len(s) % 2 == 1:
        return ':('

    if s[0] not in '(?':
        return ':('
    if s[-1] not in ')?':
        return ':('

    s = s[1:-1]
    n = len(s)
    n1 = s.count('(')
    n2 = s.count(')')

    if n1 > n // 2 or n2 > n // 2:
        return ':('

    n1 = n // 2 - n1
    n2 = n // 2 - n2
    ans = []
    for i in range(len(s)):
        if s[i] != '?':
            ans.append(s[i])
        elif n1 > 0:
            ans.append('(')
            n1 -= 1
        else:
            ans.append(')')

    n = 0
    for c in ans:
        if c == '(':
            n += 1
        else:
            n -= 1
        if n < 0:
            return ':('

    if n != 0:
        return ':('

    return "(%s)" % ''.join(ans)


def parser():
    n = int(input())
    s = input()
    return s


def output(s):
    print(s)


def main():
   args = parser()
   result = solution(args)
   output(result)


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
import sys

def rint():
    return list(map(int, sys.stdin.readline().split()))
#lines = stdin.readlines()

n = int(input())
s = input()

o = s.count('(')
c = s.count(')')
ans = []
cnt = 0

ok = 0
for i in range(n):
    ans.append(s[i])

oc = o - c
if oc > 0:
    for i in range(n-1, -1, -1):
        if oc == 0:
            break
        if ans[i] =='?':
            ans[i] = ')'
            oc -= 1
    if oc !=0:
        print(':(')
        return
#print(ans)
qc = n - o - c - (o-c)
#print(qc)
if qc%2:
    print(':(')
    return

q = 0
for i in range(n):
    if q == qc:
        break
    if ans[i] == '?':
        if q < qc//2:
            ans[i] = '('
        else:
            ans[i] = ')'
        q += 1
#print(ans)
cnt = 0
for i in range(n):
    if ans[i] == '(':
        cnt += 1
    elif ans[i] == ')':
        cnt -= 1
    if cnt <= 0 and i != n-1:
        print(':(')
        return
#print(cnt)
if cnt != 0:
    print(':(')
    return
print(''.join(ans))