Problem: Polycarpus has a finite sequence of opening and closing brackets. In order not to fall asleep in a lecture, Polycarpus is having fun with his sequence. He is able to perform two operations:

  * adding any bracket in any position (in the beginning, the end, or between any two existing brackets); 
  * cyclic shift — moving the last bracket from the end of the sequence to the beginning. 



Polycarpus can apply any number of operations to his sequence and adding a cyclic shift in any order. As a result, he wants to get the correct bracket sequence of the minimum possible length. If there are several such sequences, Polycarpus is interested in the lexicographically smallest one. Help him find such a sequence.

Acorrect bracket sequence is a sequence of opening and closing brackets, from which you can get a correct arithmetic expression by adding characters "1" and "+" . Each opening bracket must correspond to a closed one. For example, the sequences "(())()", "()", "(()(()))" are correct and ")(", "(()" and "(()))(" are not.

The sequence a1 a2... an is lexicographically smaller than sequence b1 b2... bn, if there is such number i from 1 to n, thatak = bk for 1 ≤ k < i and ai < bi. Consider that "("  < ")".

Input

The first line contains Polycarpus's sequence consisting of characters "(" and ")". The length of a line is from 1 to 1 000 000.

Output

Print a correct bracket sequence of the minimum length that Polycarpus can obtain by his operations. If there are multiple such sequences, print the lexicographically minimum one.

Examples

Input

()(())


Output

(())()

Input

()(


Output

(())

Note

The sequence in the first example is already correct, but to get the lexicographically minimum answer, you need to perform four cyclic shift operations. In the second example you need to add a closing parenthesis between the second and third brackets and make a cyclic shift. You can first make the shift, and then add the bracket at the end.

Solution (in JAVA):

Solution:
import java.util.Arrays;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.List;
import java.math.BigInteger;
import java.io.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Comparator;
import java.io.IOException;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author shu_mj @ http://shu-mj.com
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		Scanner in = new Scanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskA solver = new TaskA();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskA {
    Scanner in;
    PrintWriter out;

    public void solve(int testNumber, Scanner in, PrintWriter out) {
        this.in = in;
        this.out = out;
        run();
    }

    void run() {
        char[] cs = in.next().toCharArray();
        int n = cs.length;
        int n2 = n * 2;
        cs = Algo.merge(cs, cs);
//        SuffixArray sa = new SuffixArray(cs);
//        int[] is = new int[n2];
//        for (int i = 0; i < n2; i++) is[i] = cs[i];
//        int[] sa = buildSuffixArray(is);
        int[] sa = sa(cs);
        Seg seg = new Seg(cs);
        int[] lr = new int[2];
        for (int i = 0; ; i++) {
            int id = sa[i];
            if (id < n) {
                seg.query(id, id + n, lr);
                if (lr[1] == 0) {
                    for (int j = 0; j < lr[0]; j++) out.print('(');
                    for (int j = 0; j < n; j++) out.print(cs[j + id]);
                    out.println();
                    return ;
                } else if (lr[0] == 0) {
                    for (int j = 0; j < n; j++) out.print(cs[j + id]);
                    for (int j = 0; j < lr[1]; j++) out.print(')');
                    out.println();
                    return ;
                }
            }
        }
    }
    private static interface BaseArray {
        public int get(int i);

        public void set(int i, int val);

        public int update(int i, int val);
    }

    private static class CharArray implements BaseArray {
        private char[] m_A = null;
        private int m_pos = 0;

        CharArray(char[] A, int pos) {
            m_A = A;
            m_pos = pos;
        }

        public int get(int i) {
            return m_A[m_pos + i] & 0xffff;
        }

        public void set(int i, int val) {
            m_A[m_pos + i] = (char) (val & 0xffff);
        }

        public int update(int i, int val) {
            return m_A[m_pos + i] += val & 0xffff;
        }
    }
    private static class IntArray implements BaseArray {
        private int[] m_A = null;
        private int m_pos = 0;

        IntArray(int[] A, int pos) {
            m_A = A;
            m_pos = pos;
        }

        public int get(int i) {
            return m_A[m_pos + i];
        }

        public void set(int i, int val) {
            m_A[m_pos + i] = val;
        }

        public int update(int i, int val) {
            return m_A[m_pos + i] += val;
        }
    }
    /* find the start or end of each bucket */
    private static void getCounts(BaseArray T, BaseArray C, int n, int k) {
        int i;
        for(i = 0;i < k;++i){
            C.set(i, 0);
        }
        for(i = 0;i < n;++i){
            C.update(T.get(i), 1);
        }
    }

    private static void getBuckets(BaseArray C, BaseArray B, int k, boolean end) {
        int i, sum = 0;
        if(end != false){
            for(i = 0;i < k;++i){
                sum += C.get(i);
                B.set(i, sum);
            }
        }else{
            for(i = 0;i < k;++i){
                sum += C.get(i);
                B.set(i, sum - C.get(i));
            }
        }
    }

    /* sort all type LMS suffixes */
    private static void LMSsort(BaseArray T, int[] SA, BaseArray C,
                                BaseArray B, int n, int k) {
        int b, i, j;
        int c0, c1;
		/* compute SAl */
        if(C == B){
            getCounts(T, C, n, k);
        }
        getBuckets(C, B, k, false); /* find starts of buckets */
        j = n - 1;
        b = B.get(c1 = T.get(j));
        --j;
        SA[b++] = (T.get(j) < c1) ? ~j : j;
        for(i = 0;i < n;++i){
            if(0 < (j = SA[i])){
                if((c0 = T.get(j)) != c1){
                    B.set(c1, b);
                    b = B.get(c1 = c0);
                }
                --j;
                SA[b++] = (T.get(j) < c1) ? ~j : j;
                SA[i] = 0;
            }else if(j < 0){
                SA[i] = ~j;
            }
        }
		/* compute SAs */
        if(C == B){
            getCounts(T, C, n, k);
        }
        getBuckets(C, B, k, true); /* find ends of buckets */
        for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
            if(0 < (j = SA[i])){
                if((c0 = T.get(j)) != c1){
                    B.set(c1, b);
                    b = B.get(c1 = c0);
                }
                --j;
                SA[--b] = (T.get(j) > c1) ? ~(j + 1) : j;
                SA[i] = 0;
            }
        }
    }

    private static int LMSpostproc(BaseArray T, int[] SA, int n, int m) {
        int i, j, p, q, plen, qlen, name;
        int c0, c1;
        boolean diff;

		/*
		 * compact all the sorted substrings into the first m items of SA 2*m
		 * must be not larger than n (proveable)
		 */
        for(i = 0;(p = SA[i]) < 0;++i){
            SA[i] = ~p;
        }
        if(i < m){
            for(j = i, ++i;;++i){
                if((p = SA[i]) < 0){
                    SA[j++] = ~p;
                    SA[i] = 0;
                    if(j == m){
                        break;
                    }
                }
            }
        }

		/* store the length of all substrings */
        i = n - 1;
        j = n - 1;
        c0 = T.get(n - 1);
        do{
            c1 = c0;
        }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
        for(;0 <= i;){
            do{
                c1 = c0;
            }while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
            if(0 <= i){
                SA[m + ((i + 1) >> 1)] = j - i;
                j = i + 1;
                do{
                    c1 = c0;
                }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
            }
        }

		/* find the lexicographic names of all substrings */
        for(i = 0, name = 0, q = n, qlen = 0;i < m;++i){
            p = SA[i];
            plen = SA[m + (p >> 1)];
            diff = true;
            if((plen == qlen) && ((q + plen) < n)){
                for(j = 0;(j < plen) && (T.get(p + j) == T.get(q + j));++j){
                }
                if(j == plen){
                    diff = false;
                }
            }
            if(diff != false){
                ++name;
                q = p;
                qlen = plen;
            }
            SA[m + (p >> 1)] = name;
        }

        return name;
    }

    /* compute SA and BWT */
    private static void induceSA(BaseArray T, int[] SA, BaseArray C,
                                 BaseArray B, int n, int k) {
        int b, i, j;
        int c0, c1;
		/* compute SAl */
        if(C == B){
            getCounts(T, C, n, k);
        }
        getBuckets(C, B, k, false); /* find starts of buckets */
        j = n - 1;
        b = B.get(c1 = T.get(j));
        SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
        for(i = 0;i < n;++i){
            j = SA[i];
            SA[i] = ~j;
            if(0 < j){
                if((c0 = T.get(--j)) != c1){
                    B.set(c1, b);
                    b = B.get(c1 = c0);
                }
                SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
            }
        }
		/* compute SAs */
        if(C == B){
            getCounts(T, C, n, k);
        }
        getBuckets(C, B, k, true); /* find ends of buckets */
        for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
            if(0 < (j = SA[i])){
                if((c0 = T.get(--j)) != c1){
                    B.set(c1, b);
                    b = B.get(c1 = c0);
                }
                SA[--b] = ((j == 0) || (T.get(j - 1) > c1)) ? ~j : j;
            }else{
                SA[i] = ~j;
            }
        }
    }

    /*
     * find the suffix array SA of T[0..n-1] in {0..k-1}^n use a working space
     * (excluding T and SA) of at most 2n+O(1) for a constant alphabet
     */
    private static void SA_IS(BaseArray T, int[] SA, int fs, int n, int k) {
        BaseArray C, B, RA;
        int i, j, b, m, p, q, name, newfs;
        int c0, c1;
        int flags = 0;

        if(k <= 256){
            C = new IntArray(new int[k], 0);
            if(k <= fs){
                B = new IntArray(SA, n + fs - k);
                flags = 1;
            }else{
                B = new IntArray(new int[k], 0);
                flags = 3;
            }
        }else if(k <= fs){
            C = new IntArray(SA, n + fs - k);
            if(k <= (fs - k)){
                B = new IntArray(SA, n + fs - k * 2);
                flags = 0;
            }else if(k <= 1024){
                B = new IntArray(new int[k], 0);
                flags = 2;
            }else{
                B = C;
                flags = 8;
            }
        }else{
            C = B = new IntArray(new int[k], 0);
            flags = 4 | 8;
        }

		/*
		 * stage 1: reduce the problem by at least 1/2 sort all the
		 * LMS-substrings
		 */
        getCounts(T, C, n, k);
        getBuckets(C, B, k, true); /* find ends of buckets */
        for(i = 0;i < n;++i){
            SA[i] = 0;
        }
        b = -1;
        i = n - 1;
        j = n;
        m = 0;
        c0 = T.get(n - 1);
        do{
            c1 = c0;
        }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
        for(;0 <= i;){
            do{
                c1 = c0;
            }while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
            if(0 <= i){
                if(0 <= b){
                    SA[b] = j;
                }
                b = B.update(c1, -1);
                j = i;
                ++m;
                do{
                    c1 = c0;
                }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
            }
        }
        if(1 < m){
            LMSsort(T, SA, C, B, n, k);
            name = LMSpostproc(T, SA, n, m);
        }else if(m == 1){
            SA[b] = j + 1;
            name = 1;
        }else{
            name = 0;
        }

		/*
		 * stage 2: solve the reduced problem recurse if names are not yet
		 * unique
		 */
        if(name < m){
            if((flags & 4) != 0){
                C = null;
                B = null;
            }
            if((flags & 2) != 0){
                B = null;
            }
            newfs = (n + fs) - (m * 2);
            if((flags & (1 | 4 | 8)) == 0){
                if((k + name) <= newfs){
                    newfs -= k;
                }else{
                    flags |= 8;
                }
            }
            for(i = m + (n >> 1) - 1, j = m * 2 + newfs - 1;m <= i;--i){
                if(SA[i] != 0){
                    SA[j--] = SA[i] - 1;
                }
            }
            RA = new IntArray(SA, m + newfs);
            SA_IS(RA, SA, newfs, m, name);
            RA = null;

            i = n - 1;
            j = m * 2 - 1;
            c0 = T.get(n - 1);
            do{
                c1 = c0;
            }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
            for(;0 <= i;){
                do{
                    c1 = c0;
                }while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
                if(0 <= i){
                    SA[j--] = i + 1;
                    do{
                        c1 = c0;
                    }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
                }
            }

            for(i = 0;i < m;++i){
                SA[i] = SA[m + SA[i]];
            }
            if((flags & 4) != 0){
                C = B = new IntArray(new int[k], 0);
            }
            if((flags & 2) != 0){
                B = new IntArray(new int[k], 0);
            }
        }

		/* stage 3: induce the result for the original problem */
        if((flags & 8) != 0){
            getCounts(T, C, n, k);
        }
		/* put all left-most S characters into their buckets */
        if(1 < m){
            getBuckets(C, B, k, true); /* find ends of buckets */
            i = m - 1;
            j = n;
            p = SA[m - 1];
            c1 = T.get(p);
            do{
                q = B.get(c0 = c1);
                while (q < j){
                    SA[--j] = 0;
                }
                do{
                    SA[--j] = p;
                    if(--i < 0){
                        break;
                    }
                    p = SA[i];
                }while ((c1 = T.get(p)) == c0);
            }while (0 <= i);
            while (0 < j){
                SA[--j] = 0;
            }
        }
        induceSA(T, SA, C, B, n, k);
        C = null;
        B = null;
    }

    /* char */
    public static void suffixsort(char[] T, int[] SA, int n) {
        if((T == null) || (SA == null) || (T.length < n) || (SA.length < n)){
            return;
        }
        if(n <= 1){
            if(n == 1){
                SA[0] = 0;
            }
            return;
        }
        SA_IS(new CharArray(T, 0), SA, 0, n, 128);
    }

    public static int[] sa(char[] T)
    {
        int n = T.length;
        int[] sa = new int[n];
        suffixsort(T, sa, n);
        return sa;
    }

    class Seg {
        int N;
        int[] left, right;

        Seg(char[] cs) {
            int n = cs.length;
            N = Integer.highestOneBit(n) << 1;
            left = new int[N * 2];
            right = new int[N * 2];
            for (int i = 0; i < N; i++) {
                if (i < n && cs[i] == '(') {
                    left[i + N] = 0;
                    right[i + N] = 1;
                } else {
                    left[i + N] = 1;
                    right[i + N] = 0;
                }
            }
            for (int i = N - 1; i > 0; i--) {
                left[i] = left[i * 2] + Math.max(0, left[i * 2 + 1] - right[i * 2]);
                right[i] = right[i * 2 + 1] + Math.max(0, right[i * 2] - left[i * 2 + 1]);
            }
        }
        void query(int s, int t, int[] lr) {
            int l = 0, r = 0;
            while (0 < s && s + (s & -s) <= t) {
                int i = (N + s) / (s & -s);
                int nl = l + Math.max(0, left[i] - r);
                int nr = right[i] + Math.max(0, r - left[i]);
                l = nl; r = nr;
                s += s & -s;
            }
            int l2 = 0, r2 = 0;
            while (s < t) {
                int i = (N + t) / (t & -t) - 1;
                int nl = left[i] + Math.max(0, l2 - right[i]);
                int nr = r2 + Math.max(0, right[i] - l2);
                l2 = nl; r2 = nr;
                t -= t & -t;
            }
            lr[0] = l + Math.max(0, l2 - r);
            lr[1] = r2 + Math.max(0, r - l2);
        }
    }
/*

    void run2() {
        char[] cs = in.next().toCharArray();
        int n = cs.length;
        if (cs[n - 1] == '(' && cs[0] == '(' && !Algo.allTheSame(cs)) {
            int b = 0;
            while (cs[b] == '(') b++;
            cs = Algo.merge(Arrays.copyOfRange(cs, b, n), Arrays.copyOfRange(cs, 0, b));
        }
        if (cs[n - 1] == ')' && cs[0] == ')' && !Algo.allTheSame(cs)) {
            int b = 0;
            while (cs[b] == ')') b++;
            cs = Algo.merge(Arrays.copyOfRange(cs, b, n), Arrays.copyOfRange(cs, 0, b));
        }
        int[] is = new int[n];
        List<PII> ps = new ArrayList<PII>();
        for (int i = 0; i < n; i++) {
            if (cs[i] == '(') {
                if (i == 0 || cs[i] != cs[i - 1]) {
                    is[i] = -1;
                } else {
                    is[i] = is[i - 1] - 1;
                }
                if (i == n - 1 || cs[i] != cs[i + 1]) {
                    ps.add(new PII(is[i], i));
                }
            } else {
                if (i == 0 || cs[i] != cs[i - 1]) {
                    is[i] = 1;
                } else {
                    is[i] = is[i - 1] + 1;
                }
                if (i == n - 1 || cs[i] != cs[i + 1]) {
                    ps.add(new PII(is[i], i));
                }
            }
        }
//        Algo.debug(ps);
        int m = ps.size();
        int[] hs = new int[m];
        for (int i = 0; i < m; i++) {
            hs[i] = ps.get(i).x;
        }
        int[] ss = hs.clone();
        Algo.sort(ss);
        ss = Algo.unique(ss);
        for (int i = 0; i < m; i++) {
            hs[i] = Algo.lowerBound(ss, hs[i]) + 2;
        }
        hs = Algo.merge(hs, hs);
        SuffixArray sa = new SuffixArray(hs, ss.length + 5);
        int id = -1;
        for (int i = 0; ; i++) {
            if (sa.si[i] < hs.length / 2) {
                id = sa.si[i];
                break;
            }
        }
        int mid = ps.get(id).y - Math.abs(ps.get(id).x) + 1;
        int l = Algo.count(cs, '(');
        int r = n - l;
        if (l < r) {
            for (int i = l; i < r; i++) {
                out.print('(');
            }
            l = r;
        }
        for (int i = mid; i < n; i++) {
            out.print(cs[i]);
        }
        for (int i = 0; i < mid; i++) {
            out.print(cs[i]);
        }
        if (r < l) {
            for (int i = r; i < l; i++) {
                out.print(')');
            }
        }
        out.println();
    }
    class SuffixArray {
        public int n;
        public int[] cs;
        public int[] si, is;// si:= suffix array(si[0] = end); is[si[i]] = i;

        public int[] indexSort(int[] is, int max) {
            int[] c = new int[max + 1];
            for (int i : is) c[i]++;
            for (int i = 1; i < max; i++) c[i] += c[i - 1];
            int n = is.length;
            int[] si = new int[n];
            for (int i = n - 1; i >= 0; i--) si[--c[is[i]]] = i;
            return si;
        }

        public SuffixArray(int[] t, int max) {
            n = t.length;
            cs = new int[n + 1];
            System.arraycopy(t, 0, cs, 0, n);
            cs[n] = 0;// guard, minimum value and not allowed to use
            is = new int[n + 1];
            for (int i = 0; i <= n; i++) is[i] = cs[i];
            si = indexSort(is, max);
            int[] a = new int[n + 1], b = new int[n + 1];
            for (int h = 0; ; ) {
                for (int i = 0; i < n; i++) {
                    int x = si[i + 1], y = si[i];
                    b[i + 1] = b[i];
                    if (is[x] > is[y] || is[x + h] > is[y + h]) b[i + 1]++;
                }
                for (int i = 0; i <= n; i++) is[si[i]] = b[i];
                if (b[n] == n) break;
                h = Math.max(1, h << 1);
                for (int k = h; k >= 0; k -= h) {
                    Arrays.fill(b, 0);
                    b[0] = k;
                    for (int i = k; i <= n; i++) b[is[i]]++;
                    for (int i = 0; i < n; i++) b[i + 1] += b[i];
                    for (int i = n; i >= 0; i--) {
                        a[--b[si[i] + k > n ? 0 : is[si[i] + k]]] = si[i];
                    }
                    int[] tmp = si; si = a; a = tmp;
                }
            }
        }

        public int[] hs;// hs[i]:= suffix i & i+1 's LCP

        public void buildHs() {
            hs = new int[n + 1];
            for (int i = 0, h = 0; i < n; i++) {
                for (int j = si[is[i] - 1]; cs[i + h] == cs[j + h]; h++) ;
                hs[is[i] - 1] = h;
                if (h > 0) h--;
            }
        }

        public RMQ rmq;

        public void buildRMQ() {
            rmq = new RMQ(hs);
        }

        // begin from pos i,j, LCP means that Longest Common Prefix
        public int getLCP(int i, int j) {
            if (i == j) return n - i;
            return rmq.vs[rmq.query(Math.min(is[i], is[j]), Math.max(is[i], is[j]))];
        }
    }
*/

}

class Scanner {
    BufferedReader br;
    StringTokenizer st;

    public Scanner(InputStream in) {
        br = new BufferedReader(new InputStreamReader(in));
        eat("");
    }

    private void eat(String s) {
        st = new StringTokenizer(s);
    }

    public String nextLine() {
        try {
            return br.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public boolean hasNext() {
        while (!st.hasMoreTokens()) {
            String s = nextLine();
            if (s == null)
                return false;
            eat(s);
        }
        return true;
    }

    public String next() {
        hasNext();
        return st.nextToken();
    }

}

class Algo {


    public static char[] merge(char[] is, char[] js) {
        int in = is.length;
        int jn = js.length;
        char[] rs = new char[in + jn];
        System.arraycopy(is, 0, rs, 0, in);
        System.arraycopy(js, 0, rs, in, jn);
        return rs;
    }

}