Предыдущая ПСП

Дана правильная скобочная последовательность длины N.

Необходимо построить для данной последовательности предыдущую в лексикографическом порядке правильную скобочную последователельность.

Входные данные

В первой строке входного файла находится единственное натуральное число N (1 ≤ N ≤ 10^5, N – четно). В следующей строке находится правильная скобочная последовательность из N круглых скобок.

Выходные данные

В выходной файл выведите строку из N символов - предыдущую в лексикографическом порядке правильную скобочную последовательность. Если предыдущей последовательности не существует, выведите "No solution.".

Примеры