回想一下,如果可以在其中插入符号“+”和“1”以使结果是正确的算术表达式,则括号序列被认为是规则的。例如,序列“(()())”是正则序列,因为我们插入符号“+”和“1”可以得到正确的算术表达式:“((1+1)+(1+1))”。以下序列也是规则的:“()()()”、“(())”和“()”。以下序列不是常规括号序列:“)(”、“(()”和“())(()”。
在这个问题中,给定两个整数 n 和 k。您的任务是构造一个由长度为 2·n 的圆括号组成的规则括号序列,所有左括号的嵌套总和恰好等于 k。单个左括号的嵌套数等于当前左括号嵌入的括号对的数量。
例如,在序列“()(())”中,第一个左括号的嵌套等于0,第二个左括号的嵌套等于0,第三个左括号的嵌套等于1。因此嵌套的总和等于1。
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 3·105, 0 ≤ k ≤ 1018) - 左括号的数量和所需的总嵌套数。
输出
打印所需的由圆括号组成的常规括号序列。
如果没有解决方案,则打印“不可能”(不带引号)。
示例
输入 #1
3 1
输出 #1
()(())
输入 #2
4 6
输出 #2
(((())))
输入 #3
2 5
输出 #3
Impossible
注意
在语句中检查第一个示例。
在第二个示例中,答案是“(((())))”。第一个左括号的嵌套为 0,第二个左括号的嵌套为 1,第三个左括号的嵌套为 2,第四个左括号的嵌套为 3。所以嵌套的总和等于 0 + 1 + 2 + 3 = 6。
在第三种中,不可能构造规则的括号序列,因为两个左括号的最大可能嵌套总和等于 1。该嵌套总和是针对序列“(())”获得的。