# UVa 10077

## Summary

This problem involves divide & conquer but can be solved using some properties of Stern-Brocot tree.

## Explanation

Stern-Brocot tree has some beautiful properties. We don't need to design a divide & conquer fashioned code, rather there are some interesting tricks.

${\displaystyle {\frac {0}{1}},{\frac {1}{0}}}$

and then between adjacent fractions ${\displaystyle {\frac {m}{n}}}$ and ${\displaystyle {\frac {\acute {m}}{\acute {n}}}}$ we insert fraction ${\displaystyle {\frac {m+{\acute {m}}}{n+{\acute {n}}}}}$, then we obtain,

${\displaystyle {\frac {0}{1}},{\frac {1}{1}},{\frac {1}{0}}}$

Repeating this process, we get,

${\displaystyle {\frac {0}{1}},{\frac {1}{3}},{\frac {1}{2}},{\frac {2}{3}},{\frac {1}{1}},{\frac {3}{2}},{\frac {2}{1}},{\frac {3}{1}},{\frac {1}{0}}}$

and so forth. It can be proven that every irreducible fraction appears at some iteration and no fraction ever appears twice. The process can be represented graphically by means of so-called Stern-Brocot tree, named after its discoverers, Moritz Stern and Achille Brocot.

If we specify position of a fraction in the tree as a path consisting of L(eft) an R(ight) moves along the tree starting from the top (fraction ${\displaystyle {\frac {1}{1}}}$), and also define matrices,

${\displaystyle L={\begin{bmatrix}1&1\\0&1\end{bmatrix}},R={\begin{bmatrix}1&0\\1&1\end{bmatrix}}}$

then product of the matrices corresponding to the path is matrix ${\displaystyle L={\begin{bmatrix}n&{\acute {n}}\\m&{\acute {m}}\end{bmatrix}}}$ whose entries are numerators and denominators of parent fractions. For example, the path leading to fraction ${\displaystyle {\frac {3}{5}}}$ is ${\displaystyle LRL}$. The corresponding matrix product is,

${\displaystyle LRL={\begin{bmatrix}1&1\\0&1\end{bmatrix}}{\begin{bmatrix}1&0\\1&1\end{bmatrix}}{\begin{bmatrix}1&1\\0&1\end{bmatrix}}={\begin{bmatrix}2&3\\1&2\end{bmatrix}}}$

and the parents of ${\displaystyle {\frac {3}{5}}}$ are ${\displaystyle {\frac {1}{2}}}$ and ${\displaystyle {\frac {2}{3}}}$.

Continued fractions and Stern-Brocot tree are closely related. A continued fraction ${\displaystyle (a_{0};a_{1},a_{2}\dots )}$ corresponds to fraction whose path from the top is ${\displaystyle R^{a_{0}}R^{a_{1}}R^{a_{2}}\dots }$ with the last element removed. For example,

${\displaystyle {\frac {5}{3}}=1+{\frac {1}{1+{\frac {1}{2}}}}=(1;1,2)=R^{1}L^{1}R^{2-1}=RLR}$
${\displaystyle {\frac {4}{11}}=0+{\frac {1}{2+{\frac {1}{1+{\frac {1}{3}}}}}}=(0;2,1,3)=R^{0}L^{2}R^{1}L^{3-1}=LLRLL}$

Pretty much cool, huh?

## Gotchas

• Take care of the scenario when m is less than n i.e. ${\displaystyle {\frac {4}{11}}}$.

## Sample Input

5 7
878 323
1 1


## Sample Output

LRRL
RRLRRLRLLLLRLRRR