Incorrect bracket sequences
In a recent exercise for one of the parallel classes at LKSHenyata, students were tasked with writing a program to find the k-th correct bracket sequence in lexicographic order. A correct bracket sequence is defined as one that can be derived by removing all non-bracket characters from a valid arithmetic expression.
This challenge proved too easy for the students, so the instructor posed a new problem: find the k-th incorrect bracket sequence in lexicographic order, using exactly n brackets.
Can you solve this problem? Keep in mind that an opening bracket is considered less than a closing bracket.
Input
The first line contains two integers n and k (1 ≤ n ≤ 2000; 1 ≤ k ≤ 10^18).
Output
If the k-th incorrect bracket sequence of length n does not exist, output -1. Otherwise, provide the k-th incorrect bracket sequence.