Previous PDP

Easy

Execution time limit is 1 second

Runtime memory usage limit is 64 megabytes

A valid bracket sequence of length N is provided.

Your task is to find the previous valid bracket sequence in lexicographical order for the given sequence.

Input

The first line of the input contains a single natural number N (1 ≤ N ≤ 10^5, and N is even). The second line contains a valid bracket sequence consisting of N round brackets.

Output

Output a string of N characters representing the previous valid bracket sequence in lexicographical order. If there is no such sequence, output "No solution".

Examples

Input #1

Answer #1

Submissions 57

Acceptance rate 19%