paranteze

Time limit: 0.05s Memory limit: 256MB Input: Output:

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

Task

Given nn and mm, 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 TT times.

Input data

The first line contains a number TT, representing the number of tests. On the i+1i + 1-th line, there will be two numbers nin_i and mim_i, representing the input data for the ii-th case.

Output data

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

Constraints and clarifications

  • 1T1041 \leq T \leq 10^4
  • 1i=1Tni1051 \leq \displaystyle\sum_{i=1}^T n_i \leq 10^5
  • 0mini20 \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 (()).

Log in or sign up to be able to send submissions!