P10161 [DTCPC 2024] Xiaofang's Doubt 10

Xiaofang always has many doubts.

On Little C's birthday a few years ago, he received a gift: a string of length $n$ consisting only of $\text{(}$ and $\text{)}$, in which exactly $k$ substrings are valid bracket sequences. Since Xiaofang is very curious about what this gift looks like, you need to construct such a string, or output $-1$ to indicate that there is no solution. A valid bracket sequence satisfies the following conditions: - $\text{()}$ is a valid bracket sequence. - If $\text{A}$ and $\text{B}$ are valid bracket sequences, then $\text{(A)}$ and $\text{AB}$ are valid bracket sequences. - All other sequences are not valid bracket sequences. Xiaofang has many doubts, so he will ask you $T$ times.

The first line contains an integer $T$ representing the number of queries. The next $T$ lines each contain two integers $n$ and $k$ ($1\le n,k \le 10^5$, $\sum n\le 10^6$). **The input and output size of this problem is large, so please use fast I/O.**

For each query, if a solution exists, output a string of length $n$ on one line; otherwise output $-1$.

Translated by ChatGPT 5