Дванашки
Ггра "дванашки" схожа на відому гру "п'ятнадцять". Вона складається з коробочки розміром 5 рядків на 3 стовбця і дванадцяти фішок, по розміру рівних клітинці коробочки і пронумерованих числами від 1 до 12. Дві клітинки коробочки - друга і четверта у середньому стовбці - мають виступи і у них не можуть знаходитись фішки, у кожній з 13 клітинок, що залишились, може знаходитись не більше однієї фішки. Таким чином, якщо усі фішки знаходяться у коробці, то залишається ще й порожня клітинка. Ходом у грі є переміщення однієї фішки у сусідню клітинку, яка до ходу була порожньою. Наприклад, зсунувши з позиції на рис. 2 фішку 11 вгору, потім 10 вгору і 9 ліворуч, отримаємо позицію на рис. 1.
Ваша задача для заданої початкової позиції визначити найкоротшу послідовність ходів, які приводять до позиції, зображеної на рис. 1.
Вхідні дані
У першому рядку вхідного файлу знаходяться три числа - номери фішок, розміщених у першому ряду початкової позиції. У другому рядку знаходяться два числа, які задають номери фішок у другому ряді. У третьому, четвертому та п'ятому рядках вхідного файлу знаходяться відповідно три, два і три числа - номери фішок у відповідних рядах. Відсутність фішки позначається номером 0.
Вихідні дані
У першому рядку вихідного файлу повинно знаходитись одне число K - кількість ходів у найкоротшому розв'язку або -1, якщо розв'язку немає або він вимагає більше 70 ходів. У випадку, коли існує розв'язок не більше, ніж за 70 ходів, у другому рядку файла повинні знаходитись K символів, які задають послідовність ходів у розв'язку наступним чином:
символ 'U' - пересувається фішка, розміщена зверху від порожньої клітинки.
символ 'D' - пересувається фішка, розміщена знизу від порожньої клітинки.
символ 'L' - пересувається фішка, розміщена ліворуч від порожньої клітинки.
символ 'R' - пересувається фішка, розміщена праворуч від порожньої клітинки.