Магічний квадрат
Числа від 1 до 9 розміщені в квадраті 3x3 у випадковому порядку. Ви можете виконувати циклічні зсуви на один елемент у будь-якому рядку (вліво або вправо) чи стовпці (вгору або вниз). Напишіть програму, яка перетворює цей квадрат на магічний за мінімальну кількість таких операцій.
Розгляньмо приклад таких перетворень:
Вхідні дані
Вхідні дані складаються з трьох рядків. Кожен рядок містить три числа, розділені пробілами, що представляють рядок квадрата.
Зазначимо, що будь-який квадрат можна перетворити на магічний за допомогою певної кількості циклічних зсувів.
Вихідні дані
Перший рядок виходу містить ціле число n — мінімальну кількість циклічних операцій, необхідних для перетворення вхідного квадрата на магічний. Після цього йдуть n рядків, кожен з яких описує один зсув. Зсуви кодуються наступним чином:
Dx — зсув вниз стовпця x;
Ux — зсув вгору стовпця x;
Lx — зсув вліво рядка x;
Rx — зсув вправо рядка x.
Номер рядка (стовпця) x (1 ≤ x ≤ 3) записується без пробілу після символів "D", "U", "L" і "R". Рядки квадрата нумеруються зверху вниз, стовпці — зліва направо.