Скобочная последовательность — это строка, состоящая только из символов «(» и «)». Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов '1' и '+'. Например, скобочные последовательности «()()», «(())» — правильные (полученные выражения: «(1)+(1)», «((1+1)+1)»), а «)(» и «(» — нет.
Вам дано целое число \(n\). Ваша задача — построить и вывести ровно \(n\) различных правильных скобочных последовательностей длины \(2n\).
Выходные данные
Для каждого набора входных данных выведите \(n\) строк, каждая из которых должна содержать одну правильную скобочную последовательность длины ровно \(2n\). Все скобочные последовательности, которые вы выводите для одного набора входных данных, должны быть различны (хотя они могут совпадать в разных наборах входных данных). Если ответов несколько, выведите любой из них. Можно показать, что ответ всегда существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1
3
|
()()()
((()))
(()())
()
((()))
(())()
()(())
|