ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1657. Cube Snake

Time limit: 2.0 second
Memory limit: 64 MB
Problem illustration
Before the Quarterfinal contest, a team of programmers were given several puzzles from the online shop ru-toys.ru. The most insidious of them was the cube snake: once you take it incautiously, it unfolds immediately, and to fold it back into a cube you have to waste the precious contest time. That is why the programmers decided to quickly write a program that would solve the problem in the general form. The program would determine if it were possible to fold a snake of an arbitrary configuration into a cube. If yes, it would find how to do it.
Problem illustration
A snake consists of 27 small cubes that are strung, as beads, onto a strong thread. The thread is fixed inside the end cubes and goes through each of the remaining cubes from the center of one face to the center of another face. Though some of the cubes the thread goes straight, connecting opposite faces, and inside other cubes it turns, going through the centers of adjacent faces. The thread doesn't allow the cubes to move apart, but makes it possible to rotate a part of the cubes with respect to the other part. It is required to fold the snake into a 3 × 3 × 3 cube.

Input

The only input line contains 27 letters describing the snake as a sequence of “straight” (denoted by the letter “F”) and “turning” (denoted by the letter “T”) small cubes. The end cubes are considered as straight.

Output

If you can make a cube from the given snake, output 26 letters describing the sequence of folding. Each letter shows the position of a small cube (starting from the second one) with respect to the preceding small cube. This position can be at the front (“F”), behind (“B”), on the right (“R”), on the left (“L”), on top (“U”), or below (“D”).
If it is impossible to make a cube from the given snake, output “IMPOSSIBLE”.

Samples

inputoutput
FFTTTFTTFTTTFTFTTTTFTFTFTFF
UURDFFRBBUFLLDDRBRFFLLUURR
FFTFTFTFTTTTFFFTTTFTTFTTTFF
IMPOSSIBLE
Problem Author: Stanislav Vasilyev (prepared by Sergey Pupyrev)
Problem Source: NEERC 2008, Eastern subregion quarterfinals