3D Rod Maze

A 3-dimensional maze is built from a hollow cube. The cube uses integer coordinates and occupies the region from one corner $(0,0,0)$ to the opposite corner $(n-1,,n-1,,n-1)$. Each of the cube's six faces carries a 2-D maze: an $n\times n$ grid in which every cell is either solid (X) or open (a blank). Every border cell of every face is always solid, so the open cells form the interior pattern of each face.

Inside the cube sit a marker and six rods. Each rod runs from the marker straight out through one face of the cube. When a rod passes through a face it exits at the single cell picked out by the two marker coordinates that are parallel to that face. The marker may occupy a lattice point only when all six exit cells are open; if any rod would land on a solid cell, that position is blocked.

The marker starts at $(1,1,1)$ and must reach $(n-2,,n-2,,n-2)$. Each move slides the whole assembly one unit along an axis. The six moves are labelled F (Forward), B (Back), L (Left), R (Right), U (Up) and D (Down). Writing the marker position as $(x,y,z)$ with $1\le x,y,z\le n-2$:

• B increases $x$, F decreases $x$;
• L increases $y$, R decreases $y$;
• U increases $z$, D decreases $z$.

A move is legal only if the destination position stays inside the cube and is not blocked. Find a shortest sequence of moves that carries the marker from $(1,1,1)$ to $(n-2,,n-2,,n-2)$.

The input contains several test cases. Each test case begins with a line holding the integer $n$ ($4 \le n \le 30$). The next $6n$ lines describe the six faces, one after another, each face given as $n$ lines of exactly $n$ characters (each character is X for a solid cell or a space for an open cell).

The faces appear in this fixed order and orientation:

1. Forward — printed with its shared edge with the Up face along the top and its shared edge with the Right face along the right;
2. Right — Up edge on top, Back edge on the right;
3. Back — Up edge on top, Left edge on the right;
4. Left — Up edge on top, Forward edge on the right;
5. Up — Back edge on top, Left edge on the right;
6. Down — Back edge on top, Left edge on the right.

Equivalently, with $M = n-1$ and the marker at $(x,y,z)$, the rod through each face exits at the following $0$-indexed row and column of that printed face; the position is blocked if any of these six cells is solid:

The list of test cases ends with a line containing a single 0, which is not a test case.

For each test case output one line: a minimum-length sequence of moves that takes the marker from $(1,1,1)$ to $(n-2,,n-2,,n-2)$. Each character of the sequence is one of F, B, L, R, U, D. When several shortest sequences exist, output the one that is lexicographically smallest under the order $F < B < L < R < U < D$. Every test case is guaranteed to have at least one solution.