构造一个由 $$$N$$$ 字符组成的括号序列,使其保持平衡,并且其最长回文子序列 (LPS) 的长度恰好为 $$$K$$$。确定这样的构造是否可行。如果有多个可能的序列,请构造其中任何一个。
括号序列仅由字符 ( 和 ) 组成。如果每个字符(都有一个对应的字符)并且括号对正确嵌套,则括号序列是平衡的。例如,()、(())、(())() 和 ((())()) 是平衡的。然而,)(、(() 和 ()) 并不平衡。
如果一个序列向后读取的内容与向前读取的内容相同,则该序列是回文序列。例如,((, )、())( 和 (()(( ) 是回文。但是 ()、)( 和 (()) 不是回文。
通过删除零个或多个字符而不改变剩余字符的顺序,可以从另一个序列导出子序列。例如,(, )))、())( 和 (())() 是 (())() 的子序列。但是,)(( 和 ((())) 不是 (())() 的子序列。
序列的最长回文子序列(LPS)是从该序列派生的具有最大字符数的子序列,并且它是回文的。例如,序列(())()的LPS为())(,去掉第二个和第六个字符即可得到,因此(())()的LPS长度为$$$4$$$。
输入
输入由两个整数 $$$N$$$ $$$K$$$ ($$$2 \leq N \leq 2000; 1 \leq K \leq N$$$) 组成。 $$$N$$$ 是偶数。
输出
如果不存在这样的括号序列,使得它是平衡的并且其LPS的长度恰好是$$$K$$$,则输出-1。
否则,输出 $$$N$$$ 字符的字符串,表示括号序列。如果有多个可能的答案,则输出其中任何一个。
示例
输入 #1
6 4
输出 #1
(())()
输入 #2
6 3
输出 #2
(()())
输入 #3
4 1
输出 #3
-1
输入#4
14 11
输出#4
()((())()())()
注意
示例输入/输出#2 的说明
(()()) 的 LPS 是 ((( 通过删除所有 ) 字符,或 ))) 通过删除所有 ( 字符。
输出((()))也满足要求。
示例输入/输出 #3 的说明
唯一可能的平衡括号序列是 (()) 和 ()()。 (())和()()的LPS长度分别为$$$2$$$和$$$3$$$。
示例输入/输出 #4 的说明
()((())()())()的LPS为)())()())(),可以通过去掉第一个、第四个和第五个字符得到。