1278 - 括号生成

通过次数

33

提交次数

36

Time Limit : 1 秒
Memory Limit : 128 MB

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

Input

一个整数n,表示括号的对数

Output

所有 有效的 括号组合

Examples

Input

3

Output

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

Input

1

Output

()

Hint

1 <= n <= 8