#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif #define ll long long #define int ll #define ui unsigned int #define pb push_back #define ull unsigned long long #define ld long double #define pii pair<int,int> #define all(x) (x).begin(), (x).end() #define isz(x) (int)(x.size()) #define vi vector<int> #define ost tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> // mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int sz = 1e6, inf = 1e9; const ll mod = 998244353, INF = 1e18; void solve(int tc) { string s; cin >> s; int n = isz(s); if (n <= 18) { vector<string> ans; for (int mask = 0; mask < (1 << n); mask++) { string t; t.resize(n); for (int i = 0; i < n; i++) { if (mask >> i & 1) t[i] = '('; else t[i] = ')'; } bool KO = true; auto check = [](string s) -> bool { if (s.empty()) return true; stack<char> st; for (int i = 0; i < isz(s); i++) { if (s[i] == '(') st.push('('); else { if (st.empty()) return false; st.pop(); } } return (st.empty()); }; if (!check(t)) continue; for (int i = 0; i < n; i++) { string cur; for (int j = i+1; j < n; j++) { if (t[i] == '(' && t[j] == ')' && check(cur)) { if (s[i] != s[j]) { KO = false; break; } } cur += t[j]; if (!KO) break; } } if (KO) ans.push_back(t); } sort(all(ans)); cout << ans[0] << "\n"; return; } } void precompute() {} signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("err.log", "w", stderr); #endif precompute(); int t = 1; // cin >> t; for (int tc = 1; tc <= t; tc++) solve(tc); return 0; }