В некоторой клетке нижнего ряда шахматной доски стоит пешка. У нее есть всего два варианта хода: вверх и влево или вверх и вправо. Пешка может выбрать, с какой клетки нижнего ряда она начнет свое путешествие. На каждой клетке доски лежит от 0 до 9 горошин. Пешка хочет дойти до верхнего ряда, собрав как можно больше горошин. Так как там ей придется поделиться горошинами с k братьями, число горошин обязательно должно делиться на k + 1. Определите, какое наибольшее число горошин она сможет собрать, и какие ходы она должна для этого делать.
Пешка не может выбрасывать горошины, а также выходить за пределы доски. Когда пешка оказывается в какой-то клетке доски (включая первую и последнюю клетку пути), она обязательно берет все горошины.
Выходные данные
Если невозможно добраться до верхнего ряда, собрав при этом число делящееся на k + 1 количество горошин, выведите -1.
Иначе, первая строка должна содержать одно число — какое наибольшее число горошин она сможет собрать, при условии, что это число должно делиться на k + 1. Вторая строка должна содержать одно число — номер столбца клетки на нижнем ряду, откуда пешка должна начать свое путешествие. Столбцы нумеруются слева направо натуральными числами начиная с 1. Третья строка должна содержать строку из n - 1 символов — описание ходов пешки. Если пешка должна пойти вверх и влево, выведите L, если вверх и вправо, выведите R. Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 1
123
456
789
|
16
2
RL
|
|
2
|
3 3 0
123
456
789
|
17
3
LR
|
|
3
|
2 2 10
98
75
|
-1
|