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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void amin(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
inline void amax(T &x, U y) {
  if (x < y) x = y;
}
unsigned long long readTimeStampCounter() {
  unsigned a = 123456789, b = 987654321;
  asm("rdtsc;\n\t" : "=d"(a), "=a"(b));
  return (unsigned long long)a << 32 | b;
}
unsigned xor128() {
  static unsigned x = 123456789, y = 362436069,
                  z = (unsigned)(readTimeStampCounter() >> 32),
                  w = (unsigned)readTimeStampCounter();
  unsigned t = x ^ (x << 11);
  x = y;
  y = z;
  z = w;
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
struct SubstringHash {
  static const int NumMods = 4;
  static const unsigned Mods[NumMods];
  struct Hash {
    unsigned hs[NumMods];
    Hash() {
      for (int k = 0; k < NumMods; ++k) hs[k] = 0;
    }
    bool operator==(const Hash &that) const {
      bool res = true;
      for (int k = 0; k < NumMods; ++k) res &= hs[k] == that.hs[k];
      return res;
    }
    bool operator<(const Hash &that) const {
      for (int k = 0; k < NumMods; ++k)
        if (hs[k] != that.hs[k]) return hs[k] < that.hs[k];
      return false;
    }
  };
  static unsigned seeds[NumMods];
  static std::vector<Hash> powh;
  std::vector<Hash> preh;
  SubstringHash() {
    if (seeds[0] == 0) initSeeds();
  }
  static void initSeeds() {
    for (int k = 0; k < NumMods; ++k) {
      unsigned x;
      do x = xor128();
      while (x == 0 || x >= Mods[k]);
      seeds[k] = x;
    }
  }
  static void expandPowH(int newSize) {
    if ((int)powh.size() >= newSize) return;
    int oldSize = powh.size();
    powh.resize(newSize);
    if (oldSize == 0)
      for (int k = 0; k < NumMods; ++k) powh[0].hs[k] = 1;
    for (int i = std::max(1, oldSize); i < newSize; i++)
      for (int k = 0; k < NumMods; ++k)
        powh[i].hs[k] =
            (unsigned long long)powh[i - 1].hs[k] * seeds[k] % Mods[k];
  }
  template <typename V>
  void init(const V &v, int n) {
    expandPowH(n + 1);
    preh.resize(n + 1);
    preh[0] = Hash();
    for (int i = 0; i < n; i++)
      for (int k = 0; k < NumMods; ++k)
        preh[i + 1].hs[k] =
            ((unsigned long long)preh[i].hs[k] * seeds[k] % Mods[k] + v[i]) %
            Mods[k];
  }
  Hash hash(int j) const { return preh[j]; }
  Hash hash(int i, int j) const {
    if (i == 0) return hash(j);
    Hash res;
    for (int k = 0; k < NumMods; ++k) {
      unsigned x = preh[j].hs[k] + Mods[k] -
                   (unsigned)((unsigned long long)preh[i].hs[k] *
                              powh[j - i].hs[k] % Mods[k]);
      res.hs[k] = x >= Mods[k] ? x - Mods[k] : x;
    }
    return res;
  }
  Hash append(const Hash &h, const Hash &g, int glen) const {
    Hash res;
    for (int k = 0; k < NumMods; ++k) {
      unsigned x =
          (unsigned)((unsigned long long)h.hs[k] * powh[glen].hs[k] % Mods[k]) +
          g.hs[k];
      res.hs[k] = x >= Mods[k] ? x - Mods[k] : x;
    }
    return res;
  }
};
const unsigned SubstringHash::Mods[SubstringHash::NumMods] = {
    2147483647U, 2147483629U, 2147483587U, 2147483579U};
unsigned SubstringHash::seeds[SubstringHash::NumMods];
std::vector<SubstringHash::Hash> SubstringHash::powh;
struct Sum {
  int miniLv, addLv;
  Sum() : miniLv(0), addLv(0) {}
  Sum(char c) : miniLv(c == '(' ? 0 : -1), addLv(c == '(' ? 1 : -1) {}
  Sum operator+(const Sum &that) const {
    Sum res;
    res.miniLv = min(miniLv, addLv + that.miniLv);
    res.addLv = addLv + that.addLv;
    return res;
  }
};
struct GetRangeSegmentTree {
  static Sum combineVal(const Sum &x, const Sum &y) { return x + y; }
  static void combinesVal(Sum &x, const Sum &y) { x = x + y; }
  static Sum identityVal() { return Sum(); }
  vector<Sum> nodes;
  int n;
  void init(int n_, const Sum &v = Sum()) { init(vector<Sum>(n_, v)); }
  void init(const vector<Sum> &u) {
    n = 1;
    while (n < (int)u.size()) n *= 2;
    nodes.resize(n, identityVal());
    nodes.insert(nodes.end(), u.begin(), u.end());
    nodes.resize(n * 2, identityVal());
    for (int i = n - 1; i > 0; --i)
      nodes[i] = combineVal(nodes[i * 2], nodes[i * 2 + 1]);
  }
  Sum get(int i) { return nodes[i + n]; }
  Sum getWhole() const { return nodes[1]; }
  Sum getRange(int l, int r) const {
    Sum m = identityVal();
    int indices[64];
    int k = 0;
    for (; l && l + (l & -l) <= r; l += l & -l)
      combinesVal(m, nodes[(n + l) / (l & -l)]);
    for (; l < r; r -= r & -r) indices[k++] = (n + r) / (r & -r) - 1;
    while (--k >= 0) combinesVal(m, nodes[indices[k]]);
    return m;
  }
  Sum getRangeCommutative(int l, int r) const {
    Sum m = identityVal();
    for (; l && l + (l & -l) <= r; l += l & -l)
      combinesVal(m, nodes[(n + l) / (l & -l)]);
    for (; l < r; r -= r & -r) combinesVal(m, nodes[(n + r) / (r & -r) - 1]);
    return m;
  }
  void set(int i, const Sum &x) {
    i += n;
    nodes[i] = x;
    for (i >>= 1; i > 0; i >>= 1)
      nodes[i] = combineVal(nodes[i * 2], nodes[i * 2 + 1]);
  }
};
SubstringHash::Hash getHash(int h1, int n, int i1, int mid,
                            const SubstringHash &subhS,
                            const SubstringHash &subhO,
                            const SubstringHash &subhC) {
  if (mid <= h1)
    return subhO.hash(0, mid);
  else if (mid <= h1 + n)
    return subhS.append(subhO.hash(0, mid), subhS.hash(i1, i1 + (mid - h1)),
                        mid - h1);
  else
    return subhC.append(
        subhS.append(subhO.hash(0, mid), subhS.hash(i1, i1 + n), n),
        subhC.hash(0, mid - h1 - n), mid - h1 - n);
}
char getChar(int h1, int n, int i1, int mid, const char *S) {
  if (mid < h1)
    return '(';
  else if (mid < h1 + n)
    return S[i1 + (mid - h1)];
  else
    return ')';
}
bool compare(int n, int len1, int len2, int i1, int i2, int h1, int h2,
             const char *S, const SubstringHash &subhS,
             const SubstringHash &subhO, const SubstringHash &subhC) {
  if (len1 != len2) return len1 < len2;
  int len = len1;
  int l = 0, u = len;
  while (u - l > 0) {
    int mid = (l + u + 1) / 2;
    SubstringHash::Hash h = getHash(h1, n, i1, mid, subhS, subhO, subhC);
    SubstringHash::Hash g = getHash(h2, n, i2, mid, subhS, subhO, subhC);
    if (h == g)
      l = mid;
    else
      u = mid - 1;
  }
  return getChar(h1, n, i1, l, S) < getChar(h2, n, i2, l, S);
}
int main() {
  char *S = new char[2000001];
  char *ans = new char[2000001];
  while (~scanf("%s", S)) {
    int n = strlen(S);
    for (int(i) = 0; (i) < (int)(n); ++(i)) S[n + i] = S[i];
    S[n + n] = 0;
    SubstringHash subhS, subhO, subhC;
    subhS.init(S, n + n);
    string O(n + n, '('), C(n + n, ')');
    subhO.init(O, O.size());
    subhC.init(C, C.size());
    int minLen = 0x3f3f3f3f;
    int minHead = 0, minPos = -1;
    GetRangeSegmentTree segt;
    segt.init(vector<Sum>(S, S + (n + n)));
    for (int(i) = 0; (i) < (int)(n); ++(i)) {
      Sum sum = segt.getRange(i, i + n);
      int len = n + sum.addLv + -sum.miniLv * 2;
      int head = -sum.miniLv;
      if (compare(n, len, minLen, i, minPos, head, minHead, S, subhS, subhO,
                  subhC)) {
        minLen = len;
        minPos = i;
        minHead = head;
      }
    }
    char *p = ans;
    for (int(k) = 0; (k) < (int)(minHead); ++(k)) *(p++) = '(';
    for (int(i) = 0; (i) < (int)(n); ++(i)) *(p++) = S[minPos + i];
    for (int(i) = 0; (i) < (int)(minLen - n - minHead); ++(i)) *(p++) = ')';
    *p = 0;
    puts(ans);
  }
  return 0;
}