[DTCPC 2024] 小方的疑惑 10
题目背景
小方一直有很多疑惑。
题目描述
小 C 在几年前的生日那天收到了一个礼物:一个长度为 $n$ 的只包含 $\text{(}$ 和 $\text{)}$ 的字符串,其中恰好有 $k$ 个子串为合法的括号序列。
由于小方很疑惑这个礼物长什么样,所以你要构造一个这样的字符串,或者输出 $-1$ 表示无解。
合法的括号序列满足以下条件:
- $\text{()}$ 是合法的括号序列。
- 若 $\text{A}$ 和 $\text{B}$ 是合法的括号序列,则 $\text{(A)}$ 和 $\text{AB}$ 是合法的括号序列。
- 其它序列均不是合法的括号序列。
小方有很多疑惑,所以他会询问你 $T$ 次。
输入输出格式
输入格式
第一行一个整数 $T$ 表示询问次数。
接下来 $T$ 行,每行两个整数 $n$ 和 $k$($1\le n,k \le 10^5$,$\sum n\le 10^6$)。
**本题输入输出量较大,请使用较为快速的输入输出方式。**
输出格式
对于每次询问,如果有解,输出一行一个长度为 $n$ 的字符串,否则输出 $-1$。
输入输出样例
输入样例 #1
3
5 2
5 3
5 4
输出样例 #1
(())(
()()(
-1