Пятнашки - это популярная головоломка, придумання в \textbf{1878} году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина коробки в четыре раза больше длины стороны костяшек, соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры - перемещая костяшки по коробке, добиться упорядочивания их по номерам так, как показано на следующе картинке. \includegraphics{https://static.e-olymp.com/content/c8/c85f5016a8982f0868dc00781e0ae4e9163fd8b3.jpg} Допустимые ходы можно описать в терминах перемещения пустой клетки: её переместить вправо ("\textbf{R}"), влево("\textbf{L}"), вверх ("\textbf{U}") или вниз ("\textbf{D}"), меннясь местами с соседней костяшкой в соответствующем направлении. Вы должны по начальному состоянию головоломки определить кратчайшую последовательность ходов, ведущих в итоге к упорядоченному состоянию. \InputFile Входной файл состоит из \textbf{4} строк. В каждой записано по \textbf{4} числа от \textbf{0} до \textbf{15}, которые задают номера костяшек, находящихся в соответствующих клетках в начальном состоянии головоломки (\textbf{0} соответствует пустой клетке). Каждое из чисел встречается по одному разу. \OutputFile В выходной файл необходимо вывести одну строку. Если для заданного состояния не существует решения, выведите "\textbf{NO SOLUTION}". Если же решение есть, то эта строка должна определять кратчайшую последовательность ходов, которая приводит головоломку к требуемому финальному состоянию. Если длина оптимальной последовательности превышает \textbf{45} ходов, выведите вместо неё строку "\textbf{TOO LONG}".