The Rubik's Cube is often said to be the best-selling toy of all time
(given suitable restrictions). Invented in 1974 by Ernő Rubik, a
Hungarian sculptor and professor of architecture, it takes the
appearance of a large cube divided into smaller cubies, three to
an edge. Centre cubies have one face exposed; edge cubies have two; and
corner cubies have three. Each exposed cubie face has a sticker on it;
other than this, all cubies are identical. Stickers are merely coloured
squares, and cannot be distinguished from -degree rotations of
themselves. In a solved configuration of the cube, all stickers on a
particular face have the same colour. A special internal mechanism takes
the place of the -th cubie inside the cube; it holds the cubies
together and allows *rotation* of any of the cube's six faces. When a
face is rotated, each one of the nine cubies on that face revolves
around the centre (although the centre is not visibly affected), taking
their stickers along with them, without disturbing any of the other
cubies. The overall shape of the cube is not changed by rotation, but
the configuration of the stickers is changed.

If one holds the cube such that one of the faces is pointed directly at
oneself, it is possible to assign a notation to the faces of the cube –
`F`

for front (the face directly visible), `U`

for up, `D`

for down, `L`

for
left, `R`

for right, and `B`

for back (the face opposite the front face).
From this it is only a small step to a notation for rotations. A
-degree clockwise rotation is denoted by the letter corresponding to
the face to be rotated; a -degree rotation is denoted by the letter
followed by the numeral ; and a -degree counterclockwise rotation is
denoted by the letter followed by a single quote (`'`

). For example, `R'D2F`

means to rotate the right face counterclockwise, then rotate the bottom
face degrees, then rotate the front face clockwise. Order is
important. Any rotation, whether it is clockwise, counterclockwise, or
degrees, is considered a single *face turn*, often shortened to
*move*.

In this problem, a configuration of the Rubik's cube will be represented by a net, such as the following:

```
1 1 1
1 1 1
1 1 1
2 2 2 3 3 3 4 4 4 5 5 5
2 2 2 3 3 3 4 4 4 5 5 5
2 2 2 3 3 3 4 4 4 5 5 5
6 6 6
6 6 6
6 6 6
```

Each block represents the nine stickers of a face. The actual
configuration represented by this net may be determined by folding it
into the three-dimensional cube shape, and holding it such that the
uppermost block forms the `U`

face and the leftmost block forms the `L`

face. Similarly, the centre block represents the `F`

face, the block to
the right represents the `R`

face, the rightmost block represents the `B`

face, and the bottom block represents the `D`

face. This configuration is
solved because all the stickers on each face match. On the other hand,
the following configuration:

```
3 1 1
3 1 1
3 1 1
2 2 2 6 3 3 4 4 4 5 5 1
2 2 2 6 3 3 4 4 4 5 5 1
2 2 2 6 3 3 4 4 4 5 5 1
5 6 6
5 6 6
5 6 6
```

requires a clockwise twist of the `L`

face in order to restore to the
solved configuration above. Note that it is not necessarily the numerals
to used to denote the faces; one could just as well use the letters
to , or perhaps `W R B O G Y`

for white, red, blue, orange, green, and
yellow, a popular set of colours for the stickers.

Given a configuration of the Rubik's cube, you are to find a sequence of moves that restores it to a "solved" configuration.

#### Input Specification

Nine lines in the format described above.

#### Output Specification

A string on a single line in the format given, that is, matching the
regular expression `^([UDLRFB][2']?)*$`

, no longer than characters,
that corresponds to a sequence of moves that restores the configuration
in the input to a solved configuration. This will always be possible.

#### Sample Input

```
3 1 1
3 1 1
3 1 1
2 2 2 6 3 3 4 4 4 5 5 1
2 2 2 6 3 3 4 4 4 5 5 1
2 2 2 6 3 3 4 4 4 5 5 1
5 6 6
5 6 6
5 6 6
```

#### Sample Output

`L`

#### Scoring

It is known (Rokicki *et al*., 2010) that the exact upper bound on the
number of moves required to solve any legal configuration of the Rubik's
cube is . However, this requires impractical computer resources. A
gentler solution method using A* gives solutions within moves within
a reasonable length of time on a desktop computer. Now, of the test
cases, some can be solved within a small number of moves, and the
minimum number required is known; others were randomly-generated, and
this is why any solution will be accepted. Thus, your score, a number
between and inclusive, will be calculated as , where is
the number of moves used by your solution. For the easier cases, is
the minimum number of moves required; for the harder cases, is ,
although if you get more than , your score is adjusted to .

## Comments

For faces that are not the front face, what are "clockwise" and "counterclockwise" relative to?

As one would expect by convention, the normal vector.

which normal vector

The time limit....

The AC solution takes 0.021s worst case.