LEXBRAC - Bracket Sequence

Correct Bracket Sequence (CBS) is a sequence that can be obtained through following rules:

  1. An empty string is a CBS.
  2. If A is a CBS, then B = (A) is also a CBS.
  3. If A is a CBS, then B = [A] is also a CBS.
  4. If A and B are CBS, then C = AB is also a CBS.

Length of the CBS is the number of brackets in it, and this number is always even.

Assume that '(' < ')' < '[' < ']'.

CBS a1a2 ... an is lexicographically smaller than the CBS b1b2 ... bn if and only if there exists an integer i, i <= n, so that aj=bj, for each j, 1 <= j < i and ai < bi.

Illustration

Enumerate all CBS length 4 in lexicographical order: (()), ()(), ()[], ([]), [()], [[]], [](), [][].

Task

Your task is to find k-th CBS with length n in lexicographical order.

Input

Contains 2 integers n (2 .. 250) and k (1 .. 10^120)

Output

Print the k-th CBS with length n in lexicographical order.

Example

Input:
4
3

Output:
()[]

Added by:Chinh Nguyen
Date:2008-01-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET

hide comments
2016-01-11 22:37:54
straight forward DP lol
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.