Rubik's Cube Solver

The Rubik's Cube was invented by Ernő Rubik in 1974. It is a three-dimensional puzzle built from 26 smaller cubes. Each smaller cube has between one and three sides exposed, for a total of 54 exposed sides. Every exposed side carries one of six colors, and every color covers exactly nine exposed sides. You manipulate the cube by rotating any side of it 90 degrees. The cube is solved when each of its six sides is covered entirely by a single color.

You are a researcher at Rubik's University working on an algorithm that solves a cube in the fewest possible moves from any starting position. That research needs a program that reads cube configurations, performs operations on them, and decides whether the resulting cube is solved.

The input holds a starting configuration of the cube followed by one or more operations to perform on it.

A configuration occupies nine lines and is laid out like this:

      G W O
      G R R
      G B R
B R B R G Y W W W Y G O
G W B O G B Y B O W Y O
W R Y O Y B R Y R G O O
      B R Y
      B O W
      G Y W

Those nine lines follow the layout below.

Each character in the grid is the color of one exposed side of the cube. Characters on the same line are separated by a single space, and a line may begin with several spaces before its first character. The grid shows the cube unfolded and flattened out, and each group of 9 characters (a 3 × 3 array) is one side of the cube. The first 3 lines are the top of the cube. The next 3 lines hold the left, front, right, and back sides in that order. The last 3 lines are the bottom.

The configuration is followed by one or more operations, each on its own line. There are 12 possible operations, each a 90 degree rotation of one of the cube's faces of 9 smaller cubes. One rotation moves 20 colored squares: 8 on the face being rotated and 12 on the sides of the smaller cubes that make up that face. The table below lists all 12 operations with a description of how to perform each one.

The input is a non-empty series of at most 100 data sets, and no blank line separates one data set from the next. A single data set has four parts.

1. Start line, a single line reading START.
2. An initial configuration of the cube, 9 lines in total.
3. One or more operations, each on a separate line.
4. End line, a single line reading END.

A single line reading ENDOFINPUT follows the final data set.

Print exactly one line for each data set. Print Yes if the cube is solved, and No if it remains unsolved.