Three kinds of brackets are commonly used in programming. These are (), [] and {}. If we remove all characters, other than the brackets, from program statements, it is easier to check whether or not the brackets form a valid sequence. Since every opening bracket musrt have a matching close bracket, it is clear that all valid bracket sequences must have even length. However, it is also fairly obvious that sequences such as (}{) and [(]) are not valid. This problem considers all valid bracket sequences of a given length and the lexicographic order of these sequences. For example there are 18 valid sequences of length 4. In lexicographic order these are:

(()), ()(), ()[], (){}, ([]), ({}), [()], [[]], [](), [][], []{}, [{}], {()}, {[]}, {{}}, {}(), {}[], {}{}

So the first valid sequence is (()) and the 18th is {}{}. For a given length of sequence you will be given a numeric position. You must find the bracket sequence which comes at this position in the sorted set of all valid bracket sequences having this length. The problem will have several sets of data, of increasing difficulty. No sequence length will be greater than 38.

Input/Output description: The first line of the input data will contain a single integer N. N lines of data follow. Each of these lines contains 2 space-separated integers L and P. L is the length of the bracket sequence and P is the position of the particular sequence to be chosen from the sorted list. Your answer should be a single string containing all of the required sequences, separated by single spaces.

Example:

input:
7
4 15
8 896
12 73177
16 6922270
20 600569676
24 34872014990
28 7832826488228

answer:
{{}} {[]}[[]] {[[]()]}{()} {({}([]())[()])} [{[([{[]()}{}])]}()] ({}){(())}[{{{}[[]]}}()] [{[]{[][][]}[{{}}]{}}][[]]()

Thanks friends, for the feedback.

It recently occurred to me that combining the bracket validation problem with a lexicographic ordering problem could potentially produce a fun problem for CodeAbbey.

I really enjoyed designing a solution to the problem and hoped that others would also find it an interesting challenge.

I appreciate the early solutions coming in, as this provides reassurance that the problem setter and checker are working as they should.