说明

构造一个由 $N$ 个字符组成的括号序列，使其是平衡的，并且其最长回文子序列（LPS）的长度恰好为 $K$。判断是否存在这样的构造。如果存在多种可能的序列，输出任意一个即可。

括号序列仅由字符 ( 和 ) 组成。若每个字符 ( 都有对应的字符 )，且括号配对嵌套正确，则该括号序列是平衡的。例如，()、(())、(())() 和 ((())()) 都是平衡的；而 )(、(() 和 ()) 都不是平衡的。

如果一个序列正着读和反着读都相同，则称其为回文。例如，((、)、())( 和 (()(( 都是回文的；而 ()、)( 和 (()) 不是回文的。

子序列可以通过从原序列中删除零个或多个字符（不改变剩余字符的顺序）得到。例如，(、)))、())( 和 (())() 都是 (())() 的子序列；而 )(( 和 ((())) 不是 (())() 的子序列。

一个序列的最长回文子序列（LPS）是指从该序列中得到的、长度最大的回文子序列。例如，序列 (())() 的 LPS 是 ())(，可以通过删除第二个和第六个字符得到。因此，(())() 的 LPS 长度为 $4$。

输入格式

输入包含两个整数 $N$ 和 $K$（$2 \leq N \leq 2000$，$1 \leq K \leq N$）。$N$ 是偶数。

输出格式

如果不存在满足条件的平衡括号序列且其 LPS 长度恰好为 $K$，输出 $-1$。

否则，输出一个长度为 $N$ 的字符串，表示该括号序列。如果有多种答案，输出任意一个即可。

6 4

(())()

6 3

(()())

4 1

-1

14 11

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

提示

样例输入输出 #2 说明

(()()) 的 LPS 可以是 (((（删除所有 ) 字符），也可以是 )))（删除所有 ( 字符）。

输出 ((())) 也满足要求。

样例输入输出 #3 说明

唯一可能的平衡括号序列是 (()) 和 ()()。其中 (()) 和 ()() 的 LPS 长度分别为 $2$ 和 $3$。

样例输入输出 #4 说明

()((())()())() 的 LPS 是 )())()())()，可以通过删除第一个、第四个和第五个字符得到。

由 ChatGPT 4.1 翻译