Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MALFORMA - Zé Coquinho, o escultor

 

Zé Coquinho é um artesão que produz esculturas feitas com cocos. Os cocos secos são cortados ao meio e as cuias formadas pelas cascas são pintadas e utilizadas para construir as esculturas. As esculturas são muito famosas, sendo procuradas por colecionadores de todo o mundo.


Figura 1: A mais famosa escultura de coco feita por Zé Coquinho.

As esculturas de Zé Coquinho são sequências de cuias coladas umas nas outras. Uma escultura bem-formada é definida pelo seguinte conjunto de regras:

  • uma sequência vazia de cuias é uma escultura bem-formada.
  • se T é um escultura bem-formada, então uma escultura formada por (T) (ou seja uma cuia aberta para a direita, seguida de T, seguida de uma cuia aberta para a esquerda) é uma escultura bem-formada;
  • se T e S são esculturas bem-formadas, então ST (ou seja, a escultura S seguida de T) é uma escultura bem-formada.

Note que todas as esculturas bem-formadas são construídas usando apenas as regras descritas acima. Seja T uma escultura formada por cuias de coco. Se T não é uma escultura bem-formada, dizemos que T é uma escultura mal-formada.
Uma característica marcante das esculturas de Zé Coquinho é que elas nunca são bem-formadas; todas as esculturas que ele fez na sua longa vida são mal-formadas.
O Museu de Arte Moderna de Graviúna quer fazer uma exposição de esculturas de Zé Coquinho. Para organizar a exposição, o museu resolveu ordenar as esculturas em ordem lexicográfica. Na ordem lexicográfica definida pelo museu o símbolo ( vem antes do que o símbolo ). Por exemplo, ( ( ( < ( ( ) e ) ( < ) ).
O comprimento de uma escultura mal-formada é o número de cuias que a mesma possui. Dados dois inteiros N e K, você deve determinar a K-ésima escultura mal-formada de comprimento N considerando a ordem definida pelo museu. Considere que Zé Coquinho fez todas as esculturas mal-formadas de comprimento N.

 

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.
A primeira (e única) linha de cada instância contém dois inteiros N e K, onde 1 ≤ N ≤ 50 e 0 ≤ K ≤ 2N-1, indicando respectivamente o comprimento da escultura e o índice da escultura (na ordem lexicográfica) que você deve determinar.

Saída

Para cada instância imprima uma linha contendo a K-ésima escultura mal-formada de comprimento N. Caso não exista uma tal escultura imprima uma linha contendo -1.

Exemplo

Entrada:
4
4 0
4 4
6 63
7 13

Saída:
((((
())(
-1
((())()

Adicionado por:Wanderley Guimarăes
Data:2011-02-20
Tempo limite:0.280s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Seletiva para Maratona de Programacao IME-USP - 2010

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.