Числовая система Штерна-Броко

Дерево Штерна–Броко — изящный метод построения множества всех неотрицательных дробей $m/n$, где $m$ и $n$ — взаимно простые числа. Суть состоит в следующем: начинают с двух дробей и затем многократно выполняют такую операцию:

Вставляют новую дробь между каждой парой соседних дробей.

Например, на первом шаге между начальными двумя дробями вставляется одна дробь. На следующем шаге вставляются ещё две, потом — четыре и так далее. Вся структура может быть представлена в виде бесконечного бинарного дерева, и верхние уровни этого дерева выглядят следующим образом.

При таком построении сохраняется порядок, поэтому одна и та же дробь не появляется более одного раза.

На самом деле, дерево Штерна–Броко можно рассматривать как систему счисления для рациональных чисел, потому что любая положительная нескратимая дробь встречается в дереве ровно один раз. Для обозначения движения по дереву от корня к определённой дроби используются буквы $L$ и $R$: $L$ означает движение влево, $R$ — вправо. Таким образом, последовательность символов $L$ и $R$ однозначно определяет положение в дереве. Например, $LRRL$ означает, что нужно сначала пойти влево, потом вправо, снова вправо и опять влево. Мы можем считать, что $LRRL$ представляет определённую дробь. Для каждой положительной дроби существует одна-единственная такая последовательность.

Технически существует одно исключение: дроби $1/1$ соответствует пустая строка. Мы обозначаем её как $\mathbf{I}$, потому что она похожа на $1$ и расшифровывается как "identity" (единица).

В этой задаче, по заданной положительной рациональной дроби, требуется представить её в системе Штерна–Броко.