Задача X. Скобки Брюса-Партингтона ≡

Условие

Мы с моим другом ждали, что Майкрофт скажет дальше.

 — Вы, конечно, знаете о шифрах Брюса-Партингтона?

 — Только понаслышке.

 — Трудно переоценить их военное значение. Из всех государственных тайн эта охранялась особенно ревностно. И вдруг мы находим их в кармане мертвого мелкого чиновника, в центре города! С политической точки зрения это просто ужасно.

Шифр Брюса-Партингтона был основан на симметричных правильных скобочных последовательностях. Правильная скобочная последовательность (ПСП) — строка, состоящая из символов "(" и ")", построенная по определенным правилам:

1) Пустая строка — ПСП;

2) Если a — ПСП, то (a), ()a и a() — тоже ПСП.

ПСП считается симметричной при выполнении следующего условия: если i-м месте с начала строки стоит символ (, то на i-м месте с конца строки стоит символ ) и наоборот. Все симметричные ПСП одной длины шифровальщик расположил в лексикографическом порядке. Помогите ему быстро узнать, какая последовательность расположена на k-й позиции.

Формат входных данных

Единственная строка входного файла содержит два натуральных числа, записанных через пробел: n и k — длина ПСП и порядковый номер. Гарантируется четность n и корректность k.

Формат выходных данных

Выведите одну строку — ответ на вопрос задачи.

Ограничения

2 ≤ n ≤ 40

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснения к примерам

В первом примере полный набор симметричных ПСС состоит из трёх строк: ((())), (()()) и ()()(). Лексикографически открывающая скобка меньше закрывающей, поэтому на втором месте находится указанная в ответе ПСС.

Примеры тестов

6 2

(()())

12 18

()(())(())()