Неправильные скобочные последовательности
Недавно в одной из параллелей ЛКШат попросили написать программу, находящую k-ую в лексикографическом порядке правильную скобочную последовательность. Напомним, что правильной скобочной последовательностью является последовательность скобок, которую можно получить, выкинув из какого-то арифметического выражения всё кроме скобок.
Такая задача оказалась очень простой для ЛКШат, и преподаватель придумал новую задачу - найти k-ую в лексикографическом порядке неправильную скобочную последовательность из n скобок.
А Вы справитесь с этой задачей? Помните, что открывающая скобка меньше закрывающей.
Входные данные
Два целых числа n и k (1 ≤ n ≤ 2000; 1 ≤ k ≤ 10^18).
Выходные данные
Если k-ой неправильной скобочной последовательности длины n не существует, то выведите -1. Иначе выведите искомую k-ую неправильную скобочную последовательность.