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.