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... l] (1≤ l< |s|) of a string s = s_1s_2... s_{|s|} is string s_1s_2... 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≤ |s|≤ 3 ⋅ 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 ":(".
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.math.BigInteger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.TreeSet;

public final class CF_551_D2_C
{


	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}


	static String solve(String s){
		int L=s.length();
		if (L%2==1)
			return ":(";
		if (s.charAt(0)==')')
			return ":(";
		if (s.charAt(L-1)=='(')
			return ":(";
		String bob=solveIntern(s);
		if (bob==null)
			return ":(";
		return bob;
	}

	static boolean ok(char[] map){
		int op=0;
		int L=map.length;
		for (int i=0;i<L;i++){
			if (map[i]=='(')
				op++;
			if (map[i]==')')
				op--;
			if (op<0){
				return false;
			}
		}
		if (op>0)
			return false;
		return true;
	}

	static void test(){
		log("testing");
		int NTESTS=1000000;
		int L=10;
		Random r=new Random();
		int cnt=0;
		int ZNX=0;
		for (int t=0;t<NTESTS;t++){
			char[] map=new char[L];
		
			int jok=0;
			ArrayList<Integer> lst=new ArrayList<Integer>();
			for (int i=0;i<L;i++){
				int x=r.nextInt(10);
				if (x==0)
					map[i]='(';
				if (x==1)
					map[i]=')';
				if (x>=2) {
					jok++;
					lst.add(i);
					map[i]='?';
				}
			}
			String ss='('+new String(map)+')';
			String ans=solveIntern(ss);
			if (ans!=null)
				cnt++;
			else {


				String s=new String(map);
				char[] tm=s.toCharArray();
				int MX=1<<jok;
				for (int w=0;w<MX;w++){
					for (int i=0;i<jok;i++){
						int j=lst.get(i);
						if ((w&(1<<i))!=0){
							map[j]='(';
						} else
							map[j]=')';
					}

					if (ok(map)){
						log("problem");
						log(new String(map));
						for (int j:lst)
							map[j]='?';
						log("("+new String(map)+")");
						log(ss);
						return;
					}

				}


			}
		}
		log("cnt:"+cnt+" vs "+NTESTS);
		log("done");
	}

	static String solveIntern(String s){
		int joker=0;
		int op=0;
		int L=s.length();
		int[] stack=new int[L];
		char[] map=s.toCharArray();
		map[0]='(';
		map[L-1]=')';
		//if (L>2 && map[L-2]=='(')
		//	return null;
		//map[L-2]=')';
		int r=0;
		int w=0;
		log("going to first pass");
		log(new String(map));
		int a=0;
		int b=0;
		for (int i=1;i<L-1;i++){
			char  c=map[i];
			if (c=='(')
				a++;
			if (c==')')
				b++;
		}
		int target=(L-2)/2;
		if (a>target ||b>target)
			return null;
		a=target-a;
		b=target-b;
		for (int i=1;i<L-1;i++){
			char c=map[i];
			if (c=='?'){
				if (a>0) {
					map[i]='(';
					a--;
				}
				else
					if (b>0) {
						map[i]=')';
						b--;
					}
			}
		}
		
					op=0;
			for (int i=1;i<L-1;i++){
				if (map[i]=='(')
					op++;
				if (map[i]==')')
					op--;
				if (op<0){
					log("bug");
					return null;
				}
			}
			if (op>0) {
				log("bug");
				return null;

			}

		return new String(map);


	}
	static long pgcd(long a,long b){
		if (a<b)
			return pgcd(b,a);
		while (b!=0){
			long c=b;
			b=a%b;
			a=c;
		}
		return a;
	}




	// Global vars
	static BufferedWriter out;
	static InputReader reader;

	static void process() throws Exception {

		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader = new InputReader(System.in);
		//test();
		int n=reader.readInt();
		String s=reader.readString();

		String ans=solve(s);

		output(ans);

		try {
			out.close();
		} catch (Exception e) {
		}

	}

	public static void main(String[] args) throws Exception {
		process();

	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

}