eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Неправильные скобочные последовательности

Неправильные скобочные последовательности

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Недавно в одной из параллелей ЛКШат попросили написать программу, находящую k-ую в лексикографическом порядке правильную скобочную последовательность. Напомним, что правильной скобочной последовательностью является последовательность скобок, которую можно получить, выкинув из какого-то арифметического выражения всё кроме скобок.

Такая задача оказалась очень простой для ЛКШат, и преподаватель придумал новую задачу - найти k-ую в лексикографическом порядке неправильную скобочную последовательность из n скобок.

А Вы справитесь с этой задачей? Помните, что открывающая скобка меньше закрывающей.

Входные данные

Два целых числа n и k (1n2000; 1k10^18).

Выходные данные

Если k-ой неправильной скобочной последовательности длины n не существует, то выведите -1. Иначе выведите искомую k-ую неправильную скобочную последовательность.

Пример

Входные данные #1
3 1
Выходные данные #1
(((
Входные данные #2
4 5
Выходные данные #2
())(
Входные данные #3
4 20
Выходные данные #3
-1
Автор Антон Ахи
Источник Тринадцатая международная командная олимпиада школьников ЛКШ среди параллелей A, A' и B