URI Online Judge | 2075

# Zé Coquinho

By XIV Maratona de Programação IME-USP, 2010 Brazil

Timelimit: 1

Zé Coquinho is a crafstman that produces sculptures with coconuts. The dry coconuts are cut in half and the bowls formed by the shells are painted and used to build the sculptures. The sculptures are very famous, being sought by collectors worldwide.

Figure 1: The most famous coconut sculpture made by Zé Coquinho.

The sculptures of Zé Coquinho are sequences of bowls glued to each other. A well-formed sculpture is defined by the following set of rules;

• A empty sequence is a well-formed sculpture.
• If T is a well-formed sculpture, then a sculpture formed by (T) (i.e. a right opened bowl, followed by T, followed by a left opened bowl) is a well-formed sculpture.
• If T and S are well-formed sculptures, then ST (the sculpture S followed by T) is a well-formed sculpture.

Note that all the well-formed sculptures are built using only the above set of rules. Let T be a sculpture formed by coconuts' bowls. If T isn't a well-formed sculpture, we say that T is a malformed sculpture.

A striking feature of Ze Coquinho's sculptures is that they are never well-formed; all the sculptures that he did in his long live are malformed.

The Graviuna's Modern Art Museum wants to make a presentation of Ze Coquinho's sculptures. To organize the presentation, the museum decided to order the sculptures in lexicographical order. In the lexicographical order defined by the museum the symbol ( comes before the symbol ). For example, ((( < (() and )( < )).

The length of a malformed sculpture is the number of bowls that it possess.

Given two integers N and K, you must determine the K-th malformed sculpture of length N considering the order defined by the museum. Consider that Ze Coquinho made all the malformed sculptures of length N.

## Input

The input consists of several instances. The first line has a integer T that indicates the number of instances.

The first (and only) line of each instance has two integers N and K, where 1 ≤ N ≤ 50 e 1 ≤ K ≤ 2n − 1, indicating respectively the length of the sculpture and the index of the sculpture (in the lexicographical order) that you must determine.

## Output

For each instance print a line containing the K-th malformed sculpture of length N. If such sculpture doesn't exist print a line containing -1.

 Sample Input Sample Output 4 4 0 4 4 6 63 7 13 (((( ())( -1 ((())()