Кружок 202: Задачи

Правильной скобочной последовательностью называется такая последовательность круглых и квадратных скобок, которая могла бы встречаться в каком-нибудь арифметическом выражении. Например, последовательности ()[] и ([]) являются правильными скобочными последовательностями, а последовательности (][) и )()( — нет. Считается, что круглые и квадратные скобки равноправны, но круглой открывающей скобке обязательно должна соответствовать круглая закрывающая, а квадратной - квадратная.

Скобки считаются упорядоченными в таком порядке: «(», «)», «[», «]». Например, «)» больше, чем «(», но меньше, чем «[», а максимальной из всех скобок считается «]».

Говорят, что одна скобочная последовательность лексикографически меньше другой, если существует такое число \(k\), что первые \(k\) скобок в них совпадают, а \(k+1\)-я скобка в первой меньше, чем во второй.

Программист Вася выписал на бумажке все правильные скобочные последовательности длины \(2n\) таким образом, что каждая написанная скобочная последовательность лексикографически меньше следующей за ней. Он очень обрадовался, что теперь может по лексикографическому номеру скобочной последовательности найти саму последовательность (последовательности, записанные на бумажке, нумеруются, начиная с 1). Однако бумажка потерялась... А повторять эту огромную работу Васе лень... Помогите бедному Васе написать программу, которая бы выдавала правильную скобочную последовательность по ее лексикографическому номеру!