409735: GYM103714 E Не пили сук, на котором сидишь!
Description
![](https://espresso.codeforces.com/fb5b63bb5708dbfa7fc0376433a0ecd6f7ee37e2.png)
После продолжительного и изнурительного рабочего дня Нурбек заснул прямо на работе, а проснулся он в совершенно неожиданном месте. Перед ним открывался красивейший вид на город, вот только спуститься на землю он не мог. На этот раз Нурбек застрял на дереве.
Если в прошлом году Артем помог Нурбеку спуститься с высокой башни, в этот раз нужно будет действовать самостоятельно — с собой не было телефона. Зато у него в руках был топор. Откуда он у него взялся — он не помнит...
Нурбек, ничего лучше не придумав, решил попробовать рубить ветки под собой, чтобы спуститься вниз. Он заметил, что на этом дереве есть по две ветки с левой и правой стороны от ствола, длиной $$$l_i$$$ и $$$r_i$$$ соответственно. Эти ветки встречаются каждый метр $$$n$$$—метрового дерева, падать достаточно невысоко. Таким образом, Нурбек может совершать три возможные действия — перепрыгнуть на правую ветку 'R', перепрыгнуть на левую ветку 'L' или срубить ветку под собой 'S'. Изначально Нурбек сидит на левой ветке.
Нурбеку очень жалко бедное дерево, но придется рубить ветки. Помогите минимизировать ущерб дереву, срубив наименьшую сумму длин веток при спуске Нурбека на землю. Кроме того, Нурбек не хочет сидеть на дереве слишком долго. Если существует несколько способов минимизировать ущерб дереву, Нурбек хочет сделать это за минимальное количество действий.
Входные данныеПервая строка содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — размер дерева в метрах.
Следующие $$$n$$$ строк содержат два числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i, r_i \le 10^9$$$) — длина левой и правой ветки на высоте $$$i$$$ метров соответственно.
Выходные данныеВыведите строку из символов 'L', 'R' и 'S', которая покажет такой алгоритм действий Нурбека, при котором можно минимизировать ущерб дереву. Если таких строк несколько, выберите среди них любую строку с минимальным количеством действий.
ПримерВходные данные5 1 3 4 8 9 1 3 3 7 5Выходные данные
RSSSLSSПримечание
В первом примере Нурбек сначала перепрыгнет на правую ветку. Затем срубит правые ветки длиной $$$5$$$, $$$3$$$ и $$$1$$$ метр. На высоте два метра от земли Нурбек перепрыгнет на левую ветку и срубит оставшиеся ветки длинной $$$4$$$ и $$$1$$$ метр.