k-ый меандр
В этой задаче необходимо найти лексикографически k-ый меандр порядка n.
Рассмотрим прямую линию, нарисованную на плоскости. Меандром порядка n называется замкнутая плоская кривая, пересекающая прямую линию 2n раз. Меандр можно себе представить в виде замкнутой извилистой дороги, которая пересекает прямой отрезок реки по мостам. Приведенное интуитивное определение должно быть уточнено несколькими формальными условиями: кривая не должна иметь самопересечений или самокасаний, все 2n точек, где кривая пересекается с прямой, различны, и действительно являются пересечениями, а не касаниями, и более того, кривая и прямая больше не имеют общих точек, кроме указанных выше.
Определим удобный способ нарисовать меандр. Без ограничения общности предположим, что прямая располагается горизонтально, а точки пересечения расположены на единичном расстоянии друг от друга. Отметим, что точки пересечения кривой разделяют ее на 2n частей. Некоторые n частей находятся над прямой, а другие n частей под ней. Каждую из этих частей изобразим в виде полукруга, построенного на соответствующем сегменте линии как на диаметре, и расположим выше или ниже самой линии по мере необходимости. Можно доказать, что картинка, которую мы получили, является меандром: в частности, построенная таким образом кривая не имеет самопересечений или самокасаний. Обратное тоже верно: каждый меандр может быть преобразован в заданную картину непрерывными (гомеоморфными) преобразованиями.
Теперь давайте научимся записывать меандр в виде строки. Рассмотрим меандр, изображенный согласно приведенной процедуре. Будем идти по линии слева направо и делать запись каждый раз когда встретим точку пересечения. Для каждой такой точки две части кривой присоединены к ней: одна сверху и одна снизу прямой. Каждая из таких частей является полукругом, идущим налево или направо от текущей точки пересечения. Будем различать четыре возможных случая и отмечать каждый из них буквой английского алфавита:
Если оба полукруга идут вправо, будем говорить что кривая открывается в этом пересечении, обозначим это факт буквой O (Open).
Если оба полукруга идут влево, будем говорить что кривая закрывается в этом пересечении, обозначим это факт буквой C (Close).
Если нижний полукруг идет влево, а верхний вправо, будем говорить что кривая идет вверх в этом пересечении, обозначим это факт буквой U (Up).
Если верхний полукруг идет влево, а нижний вправо, будем говорить что кривая идет вниз в этом пересечении, обозначим это факт буквой D (Down).
Двигаясь слева направо, запишем 2n буквы для обозначения пересечений. Оказывается, что этой информации достаточно для однозначного восстановления меандра. Этот процесс можно представить себе в виде движения по течению реки (слева направо) и записи конфигурации дорог в непосредственной близости от мостов.
Два меандра считаются разными, если их нотации разные. Например, все восемь разных меандров порядка 3 представлены ниже.
Для заданного порядка n возьмем все различные меандры, отсортируем их лексикографически согласно нотациям. По заданному порядку n и числу k выведите нотацию лексикографически k-го меандра порядка n.
Входные данные
Два целых числа n и k (1 ≤ n ≤ 25, 1 ≤ k ≤ 10^11): порядок и номер меандра. Гарантируется, что меандр с указанными параметрами существует.
Выходные данные
Вывести строку из 2n букв: нотацию меандра, являющегося k-ым в лексикографически отсортированном списке меандров порядка n.