Двумерный массив называется скобочным массивом, если в каждой клетки находится одна из двух возможных скобочек — «(» или «)». Путь по клеткам двумерного массива называется монотонным, если любые две последовательные клетки в пути имеют общую сторону, и при этом каждая клетка пути находится либо ниже, либо правее предыдущей.
Двумерный скобочный массив размером n × m называется правильным скобочным массивом, если любая строка, полученная выписыванием скобочек на каком-то монотонном пути из клетки (1, 1) в клетку (n, m), образует правильную скобочную последовательность.
Определим операцию сравнения двух правильных скобочных массивов (a и b) следующим образом. Пусть задан двумерный массив приоритетов (p) — двумерный массив, заполненный различными целыми числами от 1 до nm. Найдем такую позицию (i, j) в двумерном массиве, что ai, j ≠ bi, j. Если таких позиций несколько, выберем ту, где число pi, j минимально. Если ai, j = «(», то a < b, иначе a > b. Если позиция (i, j) не найдена, то массивы считаются равными.
Ваша задача — найти k-ый двумерный правильный скобочный массив. Гарантируется, что для заданных размеров n и m будет существовать не менее k двумерных правильных скобочных массивов.
Примечание
В первом примере существует лишь один правильный скобочный двумерный массив.
Во втором и третьем примерах существует по два варианта.
Напомним, что скобочная последовательность называется правильной, если путем вставки в нее символов «+» и «1» можно получить из нее корректное математическое выражение. Например, последовательности «(())()», «()» и «(()(()))» — правильные, в то время как «)(», «(()» и «(()))(» — нет.