C. Sum of Nestings

回想一下，括号序列被认为是规则的，如果可以在其中插入符号 '_+_' 和 '_1_'，使得结果是一个正确的算术表达式。例如，序列 "_(()())_" 是规则的，因为我们可以通过插入符号 '_+_' 和 '_1_' 得到正确的算术表达式："_((1+1)+(1+1))_"。以下序列也是规则的括号序列："_()()()_"、"_(())_" 和 "_()_"。以下序列不是规则的括号序列："_)(_"、"_(()_" 和 "_())(()_"。 在本题中，给定两个整数 #cf_span[n] 和 #cf_span[k]。你的任务是构造一个由圆括号组成的、长度为 #cf_span[2·n] 的规则括号序列，使得所有左括号的嵌套深度之和恰好等于 #cf_span[k]。单个左括号的嵌套深度等于包含该左括号的括号对的数量。 例如，在序列 "_()(())_" 中，第一个左括号的嵌套深度为 #cf_span[0]，第二个左括号的嵌套深度为 #cf_span[0]，第三个左括号的嵌套深度为 #cf_span[1]。因此，嵌套深度总和为 #cf_span[1]。 第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 3·105], #cf_span[0 ≤ k ≤ 1018]) —— 分别表示左括号的数量和所需的嵌套深度总和。 请输出所要求的由圆括号组成的规则括号序列。 如果无解，请输出 "_Impossible_"（不含引号）。 题目描述中已分析第一个示例。 在第二个示例中，答案是 "_(((())))_"。第一个左括号的嵌套深度为 #cf_span[0]，第二个为 #cf_span[1]，第三个为 #cf_span[2]，第四个为 #cf_span[3]。因此，嵌套深度总和为 #cf_span[0 + 1 + 2 + 3 = 6]。 在第三个示例中，无法构造出合法的括号序列，因为两个左括号所能达到的最大嵌套深度总和为 #cf_span[1]，该值由序列 "_(())_" 实现。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 3·105], #cf_span[0 ≤ k ≤ 1018]) —— 分别表示左括号的数量和所需的嵌套深度总和。 ## Output 请输出所要求的由圆括号组成的规则括号序列。如果无解，请输出 "_Impossible_"（不含引号）。 [samples] ## Note 第一个示例已在题目描述中分析。在第二个示例中，答案是 "_(((())))_"。第一个左括号的嵌套深度为 #cf_span[0]，第二个为 #cf_span[1]，第三个为 #cf_span[2]，第四个为 #cf_span[3]。因此，嵌套深度总和为 #cf_span[0 + 1 + 2 + 3 = 6]。在第三个示例中，无法构造出合法的括号序列，因为两个左括号所能达到的最大嵌套深度总和为 #cf_span[1]，该值由序列 "_(())_" 实现。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of opening brackets. Let $ k \in \mathbb{Z}_{\geq 0} $ be the required total nesting sum. A **regular bracket sequence** of length $ 2n $ is a string of $ n $ opening brackets `(` and $ n $ closing brackets `)` such that every prefix has at least as many opening as closing brackets, and the total counts are equal. The **nesting depth** of an opening bracket is the number of opening brackets that enclose it (i.e., the depth of its position in the valid parenthesization). The **total nesting sum** is the sum of nesting depths over all $ n $ opening brackets. **Constraints** 1. $ 1 \leq n \leq 3 \cdot 10^5 $ 2. $ 0 \leq k \leq 10^{18} $ **Objective** Construct a regular bracket sequence of length $ 2n $ such that the sum of nesting depths of all opening brackets equals exactly $ k $. If no such sequence exists, output "Impossible". **Feasibility Condition** Let $ k_{\min} = 0 $ (achieved by $ n $ independent pairs: `()()...()`). Let $ k_{\max} = \sum_{i=0}^{n-1} i = \frac{(n-1)n}{2} $ (achieved by a fully nested sequence: $ \underbrace{((\cdots(}_{n}\underbrace{)\cdots))}_{n} $). Then a solution exists **if and only if** $$ 0 \leq k \leq \frac{n(n-1)}{2} $$ **Construction** If feasible: - Start with $ n $ nested opening brackets: $ \underbrace{((\cdots(}_{n} $ - Then append $ n $ closing brackets: $ \underbrace{)\cdots)}_{n} $ → total nesting sum = $ \frac{n(n-1)}{2} $ - To reduce nesting sum from $ k_{\max} $ to $ k $, "flatten" the sequence by moving closing brackets leftward to break nesting levels. - Specifically: Let $ d = k_{\max} - k $. Starting from the rightmost opening bracket (depth $ n-1 $), reduce its depth by moving its matching `)` leftward to pair with an earlier `(`, thereby reducing total nesting by the amount of depth lost. This can be done greedily: for each opening bracket from right to left, determine how many closing brackets to "pull back" to reduce the total nesting by exactly $ d $. **Output** The constructed bracket sequence, or "Impossible" if $ k > \frac{n(n-1)}{2} $ or $ k < 0 $.