题目描述

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

空序列是匹配的； 如果括号序列 s 是匹配的，那么 (s) 也是匹配的；

如果括号序列 s 与 t 是匹配的，那么 st 也是匹配的。

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

输入

单个整数：表示 $n (1 \le n \le 50)$

输出

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

样例

3

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

限制

1s, 512MB 每组测试数据