构造括号序列

题目描述

你需要构造一个长度大于等于 $a$ 并且 小于等于 $b$ 的括号序列 $s$，使得 $s$ 中有 $c$ 对数对 $(i,j)$ 满足 $0\le i < j < |s|$ 且 $s_i$ 为左括号 (、$s_j$ 为右括号 )。
如果无解输出 -1。

输入格式

输入第 $1$ 行 $1$ 个数 $T$，表示数据组数。 接下来 $T$ 行，每行 $3$ 个数 $a,b,c$。

输出格式

输出共 $T$ 行，每行一个仅包含左括号 ( 和右括号 ) 的括号串 $s$。如果无解输出 -1。

样例

输入

2
1 115 3
3 4 7

输出

((()
-1

数据范围

• Subtask 1：$a=1$，$1 \le b\le 10^5$，$\sum{b}\le 2\times 10^5$。
• Subtask 2：$1\le a\le b\le 10^9$，$\sum{a} \le 2\times 10^5$。

对于所有数据，满足：

• $1\le a\le b\le 10^9$。
• $1\le T\le 100$。
• $1\le c\le 2^{50}$。

保证所有测试点均存在输出总长度不超过 $5 \times 10^7$ 个字符的正确答案。

• 时间限制：2s
• 空间限制：512 MB
• 是否有 Special Judge：是

题解

考虑构造连续的 $x$ 个左括号和连续的 $y$ 个右括号，其中 $y=x$ 或 $y=x+1$。
不难发现只要交换一个左括号和一个右括号即可构造出 $c$ 对合法括号对，且这种构造方案下生成的 $c$ 是连续的。
贪心求出长度为 $b$ 时的合法括号对数量的最大值然后判一下无解即可。
如果 $a$ 太大就在末尾放连续的左括号，显然不产生任何贡献。