func_code_string: #include <bits/stdc++.h>   using namespace std;   bool debug;   const int inf = 1e9 + 5;   const long long INF = (long long)inf * inf;   const int nax = 1e6 + 5;   const int D = 2;   const long long MM = 1000 * 1000 * 1000;   const long long m[5] = {MM + 7, MM + 9, MM + 21, MM + 33, 333333361LL};   char sl[nax];   long long preh[nax][D];   int n;   long long potega[nax][D];   long long h(pair<int, int> a, int j) {     long long x = preh[a.second][j];     if (a.first) x -= preh[a.first - 1][j];     if (x < 0) x += m[j];     x = (x * potega[n - a.first][j]) % m[j];     return x;   }   bool rowne(pair<int, int> a, pair<int, int> b) {     for (int j = 0; j <= (D)-1; ++j)       if (h(a, j) != h(b, j)) return false;     return true;   }   int porow(pair<int, int> a, pair<int, int> b) {     assert(a.second - a.first == b.second - b.first);     if (a.first > a.second) return true;     if (rowne(a, b)) return 1;     int low = 0, high = a.second - a.first;     while (low != high) {       int med = (low + high) / 2;       if (rowne(make_pair(a.first, a.first + med),                 make_pair(b.first, b.first + med)))         low = med + 1;       else         high = med;     }     if (sl[a.first + low] ==  ( ) return 0;     return 2;   }   int pref[nax];   int LICZ;   const int pot = 1024 * 1024;   int tr[2 * pot];   int mi(int a, int b) {     a += pot;     b += pot;     int ku = min(tr[a], tr[b]);     while (a < b - 1) {       ku = min(ku, tr[a + 1]);       ku = min(ku, tr[b - 1]);       a /= 2;       b /= 2;     }     return ku;   }   bool ok_podzial_szybkie(int i) {     int s1 = pref[i];     int s2 = LICZ - pref[i];     int k = 0;     if (LICZ < 0) k = -LICZ;     if (i + 1 <= n - 1 && k + mi(i + 1, n - 1) - s1 < 0) return false;     if (0 <= i && k + s2 + mi(0, i) < 0) return false;     return true;   }   bool ok_podzial(int i) {     int teraz = 0;     if (LICZ < 0) teraz = -LICZ;     for (int j = i + 1; j <= n - 1; ++j) {       if (sl[j] ==  ( )         ++teraz;       else         --teraz;       if (teraz < 0) return false;     }     for (int j = 0; j <= i; ++j) {       if (sl[j] ==  ( )         ++teraz;       else         --teraz;       if (teraz < 0) return false;     }     return true;   }   int best = -1;   bool jebaj(int i) {     if (best == -1) return true;     int kon = best + 1 + (n - 1 - (i + 1));     int pom = porow(make_pair(best + 1, kon), make_pair(i + 1, n - 1));     if (pom == 0) return false;     if (pom == 2) return true;     int kon2 = n - 1 - (kon + 1);     pom = porow(make_pair(kon + 1, n - 1), make_pair(0, kon2));     if (pom == 0) return false;     if (pom == 2) return true;     pom = porow(make_pair(0, best), make_pair(kon2 + 1, i));     if (pom == 0) return false;     return true;   }   int main(int argc, char *argv[]) {     debug = argc > 1;     scanf( %s , sl);     n = strlen(sl);     for (int i = 0; i <= (n)-1; ++i) {       if (i) pref[i] = pref[i - 1];       if (sl[i] ==  ( )         pref[i]++;       else         pref[i]--;     }     for (int i = 0; i <= (2 * pot) - 1; ++i) tr[i] = inf;     for (int i = 0; i <= (n)-1; ++i) tr[pot + i] = pref[i];     for (int i = pot - 1; i >= 1; --i) tr[i] = min(tr[2 * i], tr[2 * i + 1]);     LICZ = 0;     for (int i = 0; i <= (n)-1; ++i) {       if (sl[i] ==  ( )         ++LICZ;       else         --LICZ;     }     for (int j = 0; j <= (D)-1; ++j) {       potega[0][j] = 1;       for (int i = 1; i <= n; ++i)         potega[i][j] = ((j == 2 ? 3 : 2) * potega[i - 1][j]) % m[j];     }     for (int j = 0; j <= (D)-1; ++j)       for (int i = 0; i <= (n)-1; ++i) {         int teraz = int(sl[i] ==  ( );         preh[i][j] = ((i ? preh[i - 1][j] : 0LL) + teraz * potega[i][j]) % m[j];       }     for (int i = 0; i <= (n)-1; ++i)       if (ok_podzial_szybkie(i))         if (jebaj(i)) best = i;     assert(best != -1);     if (LICZ < 0)       for (int _ = 0; _ <= (-LICZ) - 1; ++_) printf( ( );     for (int j = best + 1; j <= n - 1; ++j) printf( %c , sl[j]);     for (int j = 0; j <= best; ++j) printf( %c , sl[j]);     if (LICZ > 0)       for (int _ = 0; _ <= (LICZ)-1; ++_) printf( ) );     puts(  );     return 0;   }   