Square
Турнир за Купата на Декана, 2014
Time Limit: 0.6s, Memory Limit: 64MiB
Докато се компилира кодът ѝ, Ели запълва времето си с различни игрички на телефона си. Сега тя е вманиачена по играта Square.

Играта представлява квадрат с три реда и три колони, като осем от деветте клетки съдържат буквите A, B, C, D, E, F, G, H (всяка буква се съдържа по веднъж), а последната е празна. Всяка от (до) четирите съседни по хоризонтала и вертикала букви на празната клетка може да бъде преместена в нея, като мястото, на което е стояла до сега тази буква става празно. С други думи, празната клетка и съседната нейна буква, която сме избрали, разменят местата си.

Целта на играта е празната клетка да се озове в долния десен ъгъл, а останалите букви да са подредени. Тоест във финалната конфигурация трябва първият ред да съдържа буквите A, B, и C (в този ред), вторият - буквите D, E, и F (в този ред), а последният - буквите G и H (в този ред), като последната му колона да е празна.

Наскоро шефът на Ели ѝ купи дейтацентър, за да може компилирането да се случва по-бързо. Сега единственият шанс на момичето да завърши една игра по време на компилиране е ако намери решение с минимален брой ходове. Помогнете ѝ, като напишете програма, която прави това.
Вход
Стандартния вход ще съдържа три реда, описващи началното състояние на дъската. Всеки ред съдържа точно по един стринг с три символа. Всеки символ е от азбуката {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', '.'}, като '.' обозначава празната клетка. Гарантирано е, че всеки от тези символи се среща точно по веднъж.
Изход
На стандартния изход изведете един ред, съдържащ стринг от азбуката {'U', 'R', 'D', 'L'} - последователност от движения, която нарежда квадратчетата по желания начин с минимален брой ходове. Стрингът, който трябва да изведете, обозначава в каква посока се мести празното квадратче по време на играта - 'U' за "нагоре", 'R' за "надясно", 'D' за "надолу" и 'L' за "наляво". Ако съществува повече от една възможна последователност от ходове с минимална дължина, изведете която и да е от тях. Гарантирано е, че ще е нужно поне едно движение (тоест, входната дъска няма да е наредена). Ако зададената дъска не може да бъде наредена, на единствен ред изведете "IMPOSSIBLE".
Примерен ВходПримерен Изход
D.B EAC GHF DLURRDD
HEB .DC GAF IMPOSSIBLE
Мрън!