You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 0.5 s

Memory Limit: 512.0 MB

Description

lets define a bracket sequence regular if :

• every opening bracket in the sequence can be paired with another similar type closing bracket to its right

some valid bracket sequence of size 6 containing \(( )\) and \([ ]\) bracket sequences :
\(()[]()\)
\(([()])\)
\((([)])\)
\([][]()\)
\(()(())\)
\([][][]\)
some invalid bracket sequence of size 6 containing \(()\) and \([]\) bracket sequences :
\())))))\)
\()(][()\)
\(([)])(\)
\((((]]]\)

Your task is to print all possible regular bracket sequence of length \(N\) in lexicographically increasing order using only \((,),[,]\) brackets.
note : \(([)]\) is a regular bracket sequence according to the given definition.
lexicographical order of brackets ( < ) < [ < ]

Input

only one line of input takes an integer \(N\)
\(1 <= N <= 15\)

Output

all possible regular bracket sequences in lexicographical order. you should not print anything if there is no regular sequence

Sample

4

(())
()()
()[]
([)]
([])
[()]
[(])
[[]]
[]()
[][]