func_code_string: #include <bits/stdc++.h>   using namespace std;   template <typename T>   T in() {     char ch;     T n = 0;     bool ng = false;     while (1) {       ch = getchar();       if (ch ==  - ) {         ng = true;         ch = getchar();         break;       }       if (ch >=  0  && ch <=  9 ) break;     }     while (1) {       n = n * 10 + (ch -  0 );       ch = getchar();       if (ch <  0  || ch >  9 ) break;     }     return (ng ? -n : n);   }   template <typename T>   inline T Dis(T x1, T y1, T x2, T y2) {     return sqrt((x1 - x2 * x1 - x2) + (y1 - y2 * y1 - y2));   }   template <typename T>   inline T POW(T B, T P) {     if (P == 0) return 1;     if (P & 1)       return B * POW(B, P - 1);     else       return (POW(B, P / 2) * POW(B, P / 2));   }   template <typename T>   inline T ABS(T a) {     if (a < 0)       return -a;     else       return a;   }   template <typename T>   inline T Gcd(T a, T b) {     if (a < 0) return Gcd(-a, b);     if (b < 0) return Gcd(a, -b);     return (b == 0) ? a : Gcd(b, a % b);   }   template <typename T>   inline T Lcm(T a, T b) {     if (a < 0) return Lcm(-a, b);     if (b < 0) return Lcm(a, -b);     return a * (b / Gcd(a, b));   }   long long Bigmod(long long base, long long power, long long MOD) {     long long ret = 1;     while (power) {       if (power & 1) ret = (ret * base) % MOD;       base = (base * base) % MOD;       power >>= 1;     }     return ret;   }   long long ModInverse(long long number, long long MOD) {     return Bigmod(number, MOD - 2, MOD);   }   int Set(int N, int pos) { return N = N | (1 << pos); }   int Reset(int N, int pos) { return N = N & ~(1 << pos); }   bool Chkbit(int N, int pos) { return (bool)(N & (1 << pos)); }   bool isVowel(char ch) {     ch = toupper(ch);     if (ch ==  A  || ch ==  U  || ch ==  I  || ch ==  O  || ch ==  E )       return true;     return false;   }   bool isConst(char ch) {     if (isalpha(ch) && !isVowel(ch)) return true;     return false;   }   int toInt(string s) {     int sm;     stringstream ss(s);     ss >> sm;     return sm;   }   long long int toLlint(string s) {     long long int sm;     stringstream ss(s);     ss >> sm;     return sm;   }   const int N = int(2e6) + 15;   int cmp(int *r, int a, int b, int l) {     return (r[a] == r[b]) && (r[a + l] == r[b + l]);   }   int wa[N], wb[N], wws[N], wv[N];   int rnk[N], height[N];   void DA(int *r, int *sa, int n, int m) {     int i, j, p, *x = wa, *y = wb, *t;     for (i = 0; i < m; i++) wws[i] = 0;     for (i = 0; i < n; i++) wws[x[i] = r[i]]++;     for (i = 1; i < m; i++) wws[i] += wws[i - 1];     for (i = n - 1; i >= 0; i--) sa[--wws[x[i]]] = i;     for (j = 1, p = 1; p < n; j *= 2, m = p) {       for (p = 0, i = n - j; i < n; i++) y[p++] = i;       for (i = 0; i < n; i++)         if (sa[i] >= j) y[p++] = sa[i] - j;       for (i = 0; i < n; i++) wv[i] = x[y[i]];       for (i = 0; i < m; i++) wws[i] = 0;       for (i = 0; i < n; i++) wws[wv[i]]++;       for (i = 1; i < m; i++) wws[i] += wws[i - 1];       for (i = n - 1; i >= 0; i--) sa[--wws[wv[i]]] = y[i];       for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)         x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;     }   }   void calheight(int *r, int *sa, int n) {     int i, j, k = 0;     for (i = 1; i <= n; i++) rnk[sa[i]] = i;     for (i = 0; i < n; height[rnk[i++]] = k)       for (k ? k-- : 0, j = sa[rnk[i] - 1]; r[i + k] == r[j + k]; k++)         ;   }   int sa[N], data[N], n;   void Deal() {     DA(data, sa, n + 1, 128);     calheight(data, sa, n);   }   char s[2000002];   int Len;   struct z {     int opn, cls;   };   z Tree[2000002 * 4];   void Update(int id, int l, int r, int pos) {     if (l == r) {       if (s[pos] ==  ( ) {         Tree[id].opn = 1;       } else         Tree[id].cls = 1;       return;     }     int mid = (l + r) / 2;     int lft = 2 * id;     int rgt = lft + 1;     if (pos <= mid) {       Update(lft, l, mid, pos);     } else {       Update(rgt, mid + 1, r, pos);     }     int mn = min(Tree[lft].opn, Tree[rgt].cls);     Tree[id].cls = Tree[lft].cls + Tree[rgt].cls - mn;     Tree[id].opn = Tree[rgt].opn + Tree[lft].opn - mn;     return;   }   z Query(int id, int l, int r, int st, int ed) {     if (st <= l && ed >= r) {       return Tree[id];     }     int mid = (l + r) / 2;     int lft = 2 * id;     int rgt = lft + 1;     if (ed <= mid) {       return Query(lft, l, mid, st, ed);     } else if (st > mid) {       return Query(rgt, mid + 1, r, st, ed);     } else {       z a, b, c;       a = Query(lft, l, mid, st, ed);       b = Query(rgt, mid + 1, r, st, ed);       int mn = min(a.opn, b.cls);       c.cls = a.cls + b.cls - mn;       c.opn = b.opn + a.opn - mn;       return c;     }   }   int dp[2000002], Close[2000002], len, dp1[2000002];   void Solve() {     int Last = -1, Last1 = -1;     for (int i = Len + 1 - 1; i >= 1; i--) {       if (s[i] ==  ) )         Last = -1;       else if (Last == -1) {         Last = i;       }       dp[i] = (Last == -1 ? 0 : (Last - i + 1));       if (s[i] ==  ( )         Last1 = -1;       else if (Last1 == -1) {         Last1 = i;       }       dp1[i] = (Last1 == -1 ? 0 : (Last1 - i + 1));     }   }   int A[4 * 2000002];   void Update(int id, int l, int r, int pos, int val) {     if (l == r) {       A[id] = height[pos];       return;     }     int mid = (l + r) / 2;     int lft = 2 * id;     int rgt = lft + 1;     if (pos <= mid) {       Update(lft, l, mid, pos, val);     } else {       Update(rgt, mid + 1, r, pos, val);     }     A[id] = min(A[lft], A[rgt]);     return;   }   int Lcp(int id, int l, int r, int st, int ed) {     if (st <= l && ed >= r) {       return A[id];     }     int mid = (l + r) / 2;     int lft = 2 * id;     int rgt = lft + 1;     if (ed <= mid) {       return Lcp(lft, l, mid, st, ed);     } else if (st > mid) {       return Lcp(rgt, mid + 1, r, st, ed);     } else {       int a, b;       a = Lcp(lft, l, mid, st, ed);       b = Lcp(rgt, mid + 1, r, st, ed);       return min(a, b);     }   }   int HandleJhamela(int id, int id1, int Opn, int mx) {     int Suru = id + min(len, dp[id]), Suru1 = id1 + min(len, dp[id1]);     int Rnk = rnk[Suru - 1], Rnk1 = rnk[Suru1 - 1];     int L1 = len + mx - Opn - Close[id], L2 = len + mx - Opn - Close[id1];     int f = 0;     if (Rnk > Rnk1) swap(Rnk, Rnk1), f = 1;     int lcp = Lcp(1, 1, n, Rnk + 1, Rnk1);     if (f) swap(Rnk, Rnk1);     if (lcp >= min(L1, L2)) {       int diff = abs(L2 - L1);       if (L1 < L2) {         if (dp1[id1 + min(len, dp[id1]) + lcp] < diff)           return id1;         else           return id;       } else {         if (dp1[id + min(len, dp[id]) + lcp] < diff)           return id;         else           return id1;       }     } else {       if (Rnk < Rnk1)         return id;       else         return id1;     }   }   int main() {     n = 0;     scanf( %s , &s);     len = strlen(s);     for (int i = len + 1 - 1; i >= 1; i--) s[i] = s[i - 1];     Len = len * 2;     for (int i = len + 1; i < Len + 1; i++) s[i] = s[i - len];     Solve();     for (int i = 1; i < Len + 1; i++) {       Update(1, 1, Len, i);       data[n] = (int)s[i];       n++;     }     data[n] = 0;     Deal();     for (int i = 1; i < n; i++) Update(1, 1, n, i, height[i]);     int mx = (1 << 28), Open = 0, Id = 0;     for (int i = 1; i < len + 1; i++) {       z ans = Query(1, 1, Len, i, (i + len - 1));       int Cst = ans.cls + ans.opn;       Close[i] = ans.opn;       int CntOpn = ans.cls + (min(len, dp[i]));       if (mx > Cst) {         mx = Cst;         Open = CntOpn;         Id = i;       } else if (mx == Cst && CntOpn > Open) {         Open = CntOpn;         Id = i;       } else if (mx == Cst && CntOpn == Open) {         Id = HandleJhamela(Id, i, CntOpn, mx);       }     }     for (int i = 0; i < Open; i++) {       printf( ( );     }     int baki = len + mx - Open - Close[Id];     int St = Id + dp[Id];     for (int i = 0; i < baki; i++) {       printf( %c , s[St + i]);     }     for (int i = 0; i < Close[Id]; i++) {       printf( ) );     }     printf(  n );     return 0;   }   