<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

179. Brackets light
time limit per test: 0.25 sec.
memory limit per test: 131072 KB
input: standard
output: standard



There is a correct brackets sequence. It's length doesn't exceed 10000 symbols.
Your task is to find next (in lexicographic order) correct brackets sequence with the same length. You may assume that '(' < ')'.

Input
The first line of the input contains correct brackets sequence. There are only '(' and ')' symbols in the input.

Output
Write sought sequence in the single line of the output or 'No solution' if solution doesn't exist.

Sample test(s)

Input
(())()

Output
()(())
Author:	Stanislav Angelyuk
Resource:	Saratov ST team Spring Contest #1
Date:	18.05.2003

<|response|>
1. Abridged problem statement  
Given a balanced parentheses string s of even length n (n ≤ 10000), find the lexicographically next balanced parentheses string of the same length, assuming '(' < ')'. If none exists, output "No solution".

2. Key observations  
- Any balanced sequence of length n has exactly n/2 '(' and n/2 ')'.  
- To get the next lexicographic string, one must change a '(' to ')' at the rightmost possible position where the result can still be completed to a balanced sequence.  
- After flipping that '(' to ')', the suffix to its right should be rebuilt in the lexicographically smallest way (all remaining '(' first, then all remaining ')') to obtain the immediate successor.

3. Full solution approach  
Let s be the input string of length n.

Step A – skip trailing minimal blocks "()":  
  • Start i = n−2.  
  • While i ≥ 0 and s[i..i+1] == "()", decrement i by 2.  
  • These "()" pairs at the end cannot be increased locally.  

Step B – skip a run of trailing ')':  
  • While i ≥ 0 and s[i] == ')', decrement i by 1.  
  • We look for a '(' to flip.  

Step C – check for failure:  
  • If i < 0 at any point, there is no position to flip, so output "No solution".

Step D – perform the "increase":  
  • At position i we have s[i] = '('. Change it to ')'.  

Step E – count prefix balances:  
  • Count how many '(' and ')' appear in s[0..i] after the flip; call them openCnt and closeCnt.  

Step F – rebuild the suffix:  
  • Total opens needed = n/2, total closes needed = n/2.  
  • remainingOpen = n/2 − openCnt  
  • remainingClose = n/2 − closeCnt  
  • The lexicographically smallest way to complete is to append remainingOpen copies of '(' followed by remainingClose copies of ')'.  

The resulting string is the next balanced sequence. This runs in O(n) time and O(n) memory.

4. C++ implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

string s;

void read() { cin >> s; }

void solve() {
    // Next balanced bracket sequence in lexicographic order, with '(' < ')'.
    // Scan from the right past the trailing "()" pairs; the first position we
    // can increment is an '(' that we flip to ')'. Among the positions before
    // and including it we count how many '(' and ')' remain, then fill the
    // suffix with the lexicographically smallest valid completion: all the
    // remaining '(' first, then all the remaining ')'. If no such '(' exists
    // there is no greater sequence and we report "No solution".

    int n = s.size();

    int i = n - 2;
    while(i >= 0 && s.substr(i, 2) == "()") {
        i -= 2;
    }

    if(i < 0) {
        cout << "No solution\n";
        return;
    }

    while(i >= 0 && s[i] == ')') {
        i--;
    }

    if(i < 0) {
        cout << "No solution\n";
        return;
    }

    s[i] = ')';

    int open = 0, close = 0;
    for(int j = 0; j <= i; j++) {
        if(s[j] == '(') {
            open++;
        } else {
            close++;
        }
    }

    int remaining_open = n / 2 - open;
    int remaining_close = n / 2 - close;

    string result = s.substr(0, i + 1);
    for(int j = 0; j < remaining_open; j++) {
        result += '(';
    }

    for(int j = 0; j < remaining_close; j++) {
        result += ')';
    }

    cout << result << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments
```python
import sys

def next_sequence(s):
    n = len(s)
    # Convert to list for mutability
    t = list(s)

    # Step A: skip trailing "()" pairs
    i = n - 2
    while i >= 0 and t[i] == '(' and t[i+1] == ')':
        i -= 2
    if i < 0:
        return "No solution"

    # Step B: skip a run of ')'
    while i >= 0 and t[i] == ')':
        i -= 1
    if i < 0:
        return "No solution"

    # Step D: flip '(' at position i to ')'
    t[i] = ')'

    # Step E: count opens and closes in prefix [0..i]
    prefix = t[:i+1]
    open_cnt = prefix.count('(')
    close_cnt = prefix.count(')')

    # Step F: rebuild suffix
    half = n // 2
    rem_open  = half - open_cnt
    rem_close = half - close_cnt

    suffix = ['(']*rem_open + [')']*rem_close
    return "".join(prefix + suffix)

if __name__ == "__main__":
    s = sys.stdin.readline().strip()
    print(next_sequence(s))
```
