Дистанционный практикум по программированию

Главная улица Вологды, соединяющая здание лицея и общежитие, представляет собой прямоугольник с вершинами в точках (0, 0), (0, 2), (N, 2), (N, 0). Ночью в Вологде был сильный снегопад (в июне тоже такое бывает, не удивляйтесь) и теперь на некоторых единичных квадратиках улицы лежит снег.

Снегоуборочная машина представляет собой отрезок длины 1, изначально расположенный так, что его концы имеют координаты (K, 0) и (K, 1). Снегоуборочная машина может за 1 секунду переместиться в горизонтальном направлении на 1, при этом ее отрезок «заметает» клетку. Если на этой клетке был снег, то он исчезает. Кроме того, машина может мгновенно переместиться на 1 вверх или вниз (при этом отрезок перемещается по прямой, на которой он лежит).

Поскольку по главной улице скоро поедет лицейский автобус, необходимо как можно скорее убрать снег. Выясните, за какое время это можно сделать и приведите последовательность действий машины, которая позволяет убрать снег за это время.

Формат входного файла

Первая строка входного файла содержит N и K (1 ≤ N ≤ 1000, 0 ≤ K ≤ N). Следующие N строк содержат по два числа каждая, первое число i+1-й строки равно 1, если на клетке (i, 0) лежит снег и 0 в противном случае. Второе число показывает, есть ли снег на клетке (i, 1).

Формат выходного файла

В первой строке выходного файла выведите количество секунд, которое потребуется, чтобы убрать снег. На следующей строке выведите последовательность действий снегоуборочной машины в следующем формате: каждое действие обозначается заглавной буквой латинского алфавита, соответствие букв действиям приведено в следующей таблице:

 

 

В процессе работы машина не должна выходить за пределы дороги. Конечное положение машины может быть любым.

Примеры

Входные данные	Выходные данные
4 0 0 0 1 1 0 0 0 1	6 RRULRRR
4 0 0 0 0 1 0 0 1 1	5 URRRRDL