//Author RufatM #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/detail/standard_policies.hpp> using namespace __gnu_pbds; using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<string> vs; #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define endl '\n' #define pb push_back #define pf push_front #define eb emplace_back #define ff first #define ss second #define all(x) begin(x),end(x) #define rall(x) rbegin(x),rend(x) #define mt19937_64 mt_rand(chrono::steady_clock::now().time_since_epoch().count()) #define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> const int MOD=1000000007; const int INF=1000000007; const ll LINF=4e18; const int MAXN=2005; bool dp[MAXN][MAXN]; int ch[MAXN][MAXN]; signed main(){ fastio; #ifndef ONLINE_JUDGE //freopen("100points.txt(i hope)","r",stdin); //freopen("100points.out(i hope)","w",stdout); #endif int t=1; //cin >> t; while(t--){ string s; cin >> s; int n = s.size(); if(n%2==1){ cout << -1 << endl; continue; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ dp[i][j] = false; ch[i][j] = -1; } } for(int len=2;len<=n;len++){ for(int i=0;i+len-1<n;i++){ int j = i + len - 1; for(int k=i+1;k<=j;k++){ if(s[i]==s[k]){ bool left; if(i+1>k-1){ left = true; } else{ left = dp[i+1][k-1]; } if(!left){ continue; } bool right; if(k+1>j){ right = true; } else{ right = dp[k+1][j]; } if(!right){ continue; } dp[i][j] = true; ch[i][j] = k; break; } } } } if(!dp[0][n-1]){ cout << -1 << endl; continue; } string b(n,'?'); vector<pii> st; st.pb({0,n-1}); while(!st.empty()){ pii cur = st.back(); st.pop_back(); int i = cur.ff; int j = cur.ss; if(i>j){ continue; } if(i==j){ continue; } int k = ch[i][j]; if(k==-1){ continue; } b[i] = '('; b[k] = ')'; if(i+1<=k-1){ st.pb({i+1,k-1}); } if(k+1<=j){ st.pb({k+1,j}); } } int bal = 0; bool ok = true; for(int i=0;i<n;i++){ if(b[i]=='('){ bal++; } else if(b[i]==')'){ bal--; } else{ ok = false; break; } if(bal<0){ ok = false; break; } } if(!ok or bal!=0){ cout << -1 << endl; continue; } cout << b << endl; } }