题目描述

如果字符序列仅由 ( 与 ) 构成，则在满足以下条件时，它是匹配的：

• 空序列是匹配的；
• 如果括号序列 s 是匹配的，那么 (s) 也是匹配的；
• 如果括号序列 s 与 t 是匹配的，那么 st 也是匹配的。

给定一个整数 $n$，请输出 $n$ 个左括号与 $n$ 个右括号可以组成的所有匹配括号序列，并且按照字典序将它们输出（如果超过 $1000$ 种，则仅输出前 $1000$ 种。）

输入格式

单个整数：表示 $n$

输出格式

若干行：每行表示一种由 $n$ 对括号组成的匹配括号序列，按照字典序排列，如果超过 $1000$ 种，则仅输出前 $1000$ 种序列。

2

(())
()()

3

((()))
(()())
(())()
()(())
()()()

数据范围

• $1\leq n\leq 50$