Числова система Штерна-Броко
Дерево Штерна-Броко - це вишуканий спосіб побудови множини всых невід'єних дробів m / n, де m і n - взаємно прості числа. Ідея полягає у тому, щоб почати з двох дробів і потім повторити нижче описану операцію стільки разів, скільки це потрібно:
Вставити між двома сусідніми дробами і .
Наприклад, перши крок дає нам одне нове входження між і :
наступний крок дасть ще два:
Наступний крок дасть ще чотири:
Весь масив можна розглядати, як нескінченне бінарне дерево, чиї верхні рівні виглядають так:
Ця конструкція зберігає порядок, так що ми не можемо отримати один і той же дріб у різних місцях.
Фактично ми можемо розглядати дерево Штерна-Броко як систему числення для подання раціональних чисел, тому що кожен додатній, нескоротний дріб зустрічається у дереві лише один раз. Будемо використовувати літери L і R для позначення того, рухаємся ми по лівій чи по правій гілці дерева, коли спускаємось від кореня дерева до певного дробу; тоді рядок, що складається з певної послідовності цих L і R, унікальним чином визначає положення у дереві. Наприклад, LRRL означає, що ми йдемо по лівій гілці від до , потім по правій до , потім по правій до, потім по лівій до. Ми можемо розглядати LRRL як подання . Довільний додатній дріб подається таким чином унікальним рядком, що складається з L і R.
Ну, скажемо, майже довільний дріб. Дробу відповідає пустий рядок. Ми будемо позначати його I, так як це схоже на 1 і є першою літерою слова "identity" (одиниця).
У цій задачі ви повинні подати заданий додатній раціональний дріб у системі числення Штерна-Броко.
Вхідні дані
Складається з декілької тестів. Кожен тест складається з двох взаємно простих натуральних чисел m та n. Останній тест містить дві одиниці та не опрацьовується.
Вихідні дані
Для кожного тесту виведіть в окремому рядку подання заданого дробу в системі числення Штерна-Броко.