You are trapped in a room with a puzzle grid painted on the floor. You are in a start square, just below the puzzle grid, facing up. Your task is to get to a target square (or suffer a terrible fate). Your first move must be to step into the main puzzle grid if you can. Once in, you may not step outside the grid unless it is onto a target square. Once you step onto a target square, you are finished and can make no further moves.

Each square in the puzzle grid has a symbol painted on it representing a possible move (up, down, left, right, clockwise, or counterclockwise). You can only move one grid square at a time and you can only turn $90$ degrees at a time. Your next move must always be one of the moves you can see painted on the floor ahead of you (this does not include the one you are standing on). You cannot change the direction you are facing unless you can see a move ahead that allows you to turn clockwise or counter-clockwise. Because of the restrictions on the direction you can face, you will often end up stepping sideways or backwards when completing this puzzle.

In the sequence of moves shown above, the user starts at the bottom, facing up. Her target is the square above the maze at the top. For her first move, the choices are UP or LEFT (just the moves she sees in front of her). She can't go left, so she chooses UP. Then her choices are UP or LEFT again and she chooses LEFT. Now her choices have changed: CLOCKWISE, COUNTERCLOCKWISE, or DOWN. She can't move down and if she turns counterclockwise, she will have no moves in front of her. So she chooses CLOCKWISE. For her next move, she can now choose from UP or CLOCKWISE.

The input will contain $10$ test cases. Each test case consists of $6$ lines of $6$ characters, representing a $4\times 4$ puzzle grid as well as all possible start and target squares around the outside of the grid. The moves are U, D, L, R, C, and B for UP, DOWN, LEFT, RIGHT, CLOCKWISE, and COUNTERCLOCKWISE respectively. The start square is marked S and can be anywhere on the bottom row. There will be five possible target squares, marked T, which can appear anywhere around the outside of the puzzle grid. Squares which are out of bounds are marked with the . character (ASCII code $46$).

Write a program to determine which of the target squares can be reached from the given start square. You should output a single line of $5$ characters, with each character representing a target square (in order from top left, scanning each row from left to right, moving downwards). If a target square is reachable, output T for that square. If not, output F.

Note that in the sample input below, there are $2$ test cases, but the real data files will contain $10$. The squares which are part of the puzzle grid are shaded below for ease of reading, but this shading will not appear in the file.

Sample Input

..TT..
TCURC.
.DLRD.
.BUBB.
.CUCCT
.TS...
.T.T..
TRCDU.
.UCLDT
.RCBL.
TDUCU.
.S....

Sample Output

TTFFT
FTFFF

Question Development Team

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org