合法的括号序列是指由括号 ( 和 ) 组成的字符串，其中左括号的数量等于右括号的数量，且字符串的任意前缀中左括号的数量不少于右括号的数量。例如，()() 是合法的括号序列，而 ())( 不是，因为前缀 ()) 中右括号的数量多于左括号。

对于给定的长度为 $2n$ 的一对括号序列，如果它们在某个位置开始不同，且在该位置前者为左括号而后者为右括号，则称前者比后者更靠前。这种排序方式等同于字典序，前提是规定 '(' < ')'。

编写一个程序：

• 从标准输入读取整数 $n$ 和 $k$。
• 找出长度为 $2n$ 的所有合法括号序列中字典序第 $k$ 小的序列（序列从 1 开始编号）。
• 将结果输出到标准输出。

输入格式

输入包含两个整数 $n$ 和 $k$ ($1 \le n \le 4\,000$, $1 \le k \le 10^{18}$)，中间用单个空格隔开。

输出格式

在第一行输出长度为 $2n$ 的括号序列，即所有长度为 $2n$ 的合法括号序列中字典序第 $k$ 小的序列。输入数据保证所求的括号序列一定存在。

样例

输入 1

3 2

输出 1

(()())