solution.[构造括号序列]

## 构造括号序列

## 题目描述

你需要构造一个长度大于等于 $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$ 太大就在末尾放连续的左括号，显然不产生任何贡献。