This problem was created by Clive Fraser aka CSFPython - thank you, Clive!
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:
(()), ()(), ()[], (){}, ([]), ({}), [()], [[]], [](), [][], []{}, [{}], {()}, {[]}, {{}}, {}(), {}[], {}{}
It is easy to deduce that lexicograpic order in ASCII is ()[]{}.
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:
{{}} {[]}[[]] {[[]()]}{()} {({}([]())[()])} [{[([{[]()}{}])]}()] ({}){(())}[{{{}[[]]}}()] [{[]{[][][]}[{{}}]{}}][[]]()