RoAlgo Contest #10 | paranteze

For a given number $n$ and a given number $m$, a sequence of parentheses is said to be good if it has a length of $n$ and exactly $m$ correctly parenthesized subsequences.

Task

Given $n$ and $m$, print a good sequence of parentheses. If it does not exist, print -1. Since this is too easy for you, you will have to do this $T$ times.

Input data

The first line contains a number $T$, representing the number of tests. On the $i + 1$-th line, there will be two numbers $n_i$ and $m_i$, representing the input data for the $i$-th case.

Output data

On the $i$-th line, print -1 or a good sequence of parentheses for the $i$-th case.

Constraints and clarifications

• $1 \leq T \leq 10^4$
• $1 \leq \displaystyle\sum_{i=1}^T n_i \leq 10^5$
• $0 \leq m_i \leq n_i^2$
• The printed sequence does not need to be correctly parenthesized.
• A sequence is called correctly parenthesized if and only if characters + and 1 can be inserted such that the obtained sequence represents a correct mathematical expression. For example, (()) and ()(()) are correctly parenthesized sequences because (1+(1+1)) and (1+1)+(1+(1+1)) are correct mathematical expressions, but (() and ())(() are not correctly parenthesized sequences.

Example

stdin

3
6 4
2 4
4 2

stdout

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

Explanation

For the first case, the correctly parenthesized subsequences are ()(()), () (first two characters), (()), and () (fourth and fifth characters).

For the second case, it can be shown that there is no solution.

For the third case, the correctly parenthesized subsequences are () and (()).