Incorrect bracket sequences#5239
In a recent exercise for one of the parallel classes at LKSHenyata, students were tasked with writing a program to find the -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 -th incorrect bracket sequence in lexicographic order, using exactly brackets.
Can you solve this problem? Keep in mind that an opening bracket is considered less than a closing bracket.
The first line contains two integers and (1 \leq n \leq 2000; 1 \leq k \leq 10^{18}).
If the -th incorrect bracket sequence of length does not exist, output -1. Otherwise, provide the -th incorrect bracket sequence.
Example 1
Example 2
Example 3