403165: GYM101055 H Zé Coquinho, the sculptor

Memory Limit:64 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Zé Coquinho, the sculptortime limit per test0.25 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

Zé Coquinho is a famous artisan that makes sculptures with coconuts. The dried coconuts are cut in half and bows are made with the shells, and used to build sculptures. The sculptures are very famous, and are searched by collectors all over the world.

This is the most famous coconut sculpture made by Zé Coquinho.

Zé Coquinho's sculptures are sequences os bowls glued to each other. A bowl open to the left is represented as ')' and a bowl open to the right is represented as '('. A well-formed sculpture is defined the following way:

  • An empty sequence of bowls is well-formed.
  • If T is well-formed, then (T) is well-formed.
  • If S and T are well-formed, the ST is well-formed.

A marking characteristic of Zé Coquinho's sculptures is that they are never well-formed.

The Museum of Modern Art of Graviúna wants to make an exposition of Zé Coquinho's works. To organize the exposition, the museum decided to ordem the sculptures in lexicographic order. The museum considers '(' comes before ')' so, for example, "(((" < "(()" < ")((". The size of an sculpture is the number of bowls used in it.

Given N and K, you should determine the Kth sculpture Zé Coquinho made, in lexicographic order. You can consider Zé Coquinho created all possible non-well-formed sculptures of size N.

Input

The first line has a single integer Q, the number of queries.

Each of the next Q lines has two integers N and K.

Limits

  • 1 ≤ Q ≤ 200
  • 1 ≤ N ≤ 50
  • 1 ≤ K ≤ 2N
Output

For each query, print a single line, the Kth sculpture of size N made by Coquinho, in lexicographic order. If there is no such sculpture, print "-1" instead.

ExampleInput
4
4 1
4 5
6 64
7 14
Output
((((
())(
-1
((())()

Source/Category

加入题单

上一题 下一题 算法标签: