Construct Parentheses String with Exactly $k$ Valid Substrings

You are given an integer $T$. For each query, you are given two integers $n$ and $k$. You need to construct a parentheses string $S$ of length $n$ (each character is either '(' or ')') such that exactly $k$ of its contiguous substrings are valid parentheses sequences.

A valid parentheses sequence is defined as follows:

• $\;()\;$ is a valid sequence.
• If $A$ and $B$ are valid sequences, then both $\;(A)\;$ and $\;AB\;$ are valid sequences.
• No other sequences are valid.

If no such string exists, output -1.

Note: A simple way to guarantee a valid substring is to use the pattern "()". However, be cautious: if two valid substrings are adjacent, their concatenation might also form a valid sequence (because concatenation of valid sequences is valid). For example, the string "()()" has three valid substrings: the first "()", the second "()", and the full string "()()". To avoid accidentally creating extra valid substrings, one approach is to separate each occurrence of "()" with an extra character so that no longer balanced substring can be formed.

A construction that produces k valid occurrences without unintended extra valid substrings is as follows (for $k \ge 1$):

Let the base string be:

$$\text{Base} = "()" + \underbrace{("(" + "()") + \cdots + ("(" + "()")}_{k-1 \text{ times}} $$

This base string has length $L = 2 + 3(k-1) = 3k - 1$ and exactly $k$ valid "()" substrings. If $n > L$, append extra ')' characters at the end (since concatenating extra ')' will not form new valid substrings).

For the case $k = 0$, note that choosing a string without the substring "()" (for example, a string consisting solely of '(' characters) will have 0 valid substrings.

Your task is to answer $T$ queries. For each query, if a valid string exists, output one such string. Otherwise, output -1.

inputFormat

The first line contains an integer $T$, the number of test cases.

Each of the next $T$ lines contains two integers $n$ and $k$, where $n$ is the length of the string to construct and $k$ is the desired number of valid parentheses substrings.

outputFormat

For each test case, output a single line containing the constructed string of length $n$ that has exactly $k$ valid parentheses substrings, or -1 if no such string exists.

sample

5
2 1
5 2
8 3
10 2
4 2

()
()(()
()(()(()
()(()))))
-1

</p>