[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