Дерево Штерна-Броко - это изящный способ построения множества всех неотрицательных дробей m / n, где m и n взаимно простые числа. Идея состоит в том, чтобы начать с двух дробей и затем повторить нижеследующую операцию столько раз, сколько это нужно:
Вставить между двумя соседними дробями и .
Например, первый шаг дает нам одно новое вхождение между и :
следующий шаг даст еще два:
Следующий шаг даст еще четыре:
Весь массив можно рассматривать, как бесконечное бинарное дерево, чьи верхние уровни выглядят так:
Эта конструкция сохраняет порядок, так что мы не можем получить одну и ту же дробь в различных местах.
Фактически мы можем рассматривать дерево Штерна-Броко как систему счисления для представления рациональных чисел, потому что каждая положительная, сокращенная дробь встречается в дереве только один раз. Будем использовать буквы L и R для обозначения того, двигаемся мы по левой или по правой ветви дерева, когда спускаемся от корня дерева к определенной дроби; тогда строка, состоящая из определенной последовательности этих L и R, уникальным образом определяет положение в дереве. Например, LRRL означает, что мы идем по левой ветви от к , затем по правой к , затем по правой к, затем по левой к . Мы можем рассматривать LRRL как представление . Любая положительная дробь представляется таким путем уникальным строкой, состоящей из L и R.
Ну, скажем, почти любая дробь. Дроби соответствует пустая строка. Мы будем обозначать ее I, так как это похоже на 1 и является первой буквой слова "identity" (единица).
В этой задаче вы должны представить данную положительную рациональную дробь в системе счисления Штерна-Броко.
Состоит из нескольких тестов. Каждый тест состоит из двух взаимно простых натуральных чисел m и n. Последний тест содержит две единицы и не обрабатывается.
Для каждого теста выведите в отдельной строке представление заданной дроби в системе счисления Штерна-Броко.