Similar Problems

0792. Game with Cube

Time limit : 1000 ms
Memory limit : 64 mb

Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Erno Rubik. Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that year. As of January 2009, 350 million cubes had been sold worldwide making it the world's top-selling puzzle game. It is widely considered to be the world's best-selling toy.

The Rubik's Cube has eight corners and twelve edges. There are 8! (40,320) ways to arrange the corner cubes. Seven can be oriented independently, and the orientation of the eighth depends on the preceding seven, giving 37 (2,187) possibilities. There are 12!/2 (239,500,800) ways to arrange the edges, since an even permutation of the corners implies an even permutation of the edges as well. (When arrangements of centers are also permitted, as described below, the rule is that the combined arrangement of corners, edges, and centers must be an even permutation.) Eleven edges can be flipped independently, with the flip of the twelfth depending on the preceding ones, giving 211 (2,048) possibilities.

The total possibilities of a Rubik’s cube are:            8! * 37 * 12!/2 * 211 = 43,252,003,274,489,856,000.

Although the number of cases is quite huge, we can still solve the magic cube b some way. It is confirmed that no matter what cases the cube is, you can solve it within just 20 turnings, quite fantastic, isn’t it?

A Rubik’s cube has six faces:

F (Front): the side currently facing the solver

B (Back): the side opposite the front

U (Up): the side above or on top of the front side

D (Down): the side opposite the top, underneath the Cube

L (Left): the side directly to the left of the front

R (Right): the side directly to the right of the front

Now, we define several moves which mean different turning of layers: U D R L F B which means turning the up, down, right, left, front back face clockwise for 90 degree. In addition, use lowercase letters u d r l f b for anticlockwise turnings. Errrrrrrrr, that’s not the end, I define more operations: X Y Z for turning the middle layer (behind U R F) clockwise for 90 degree. Also, lowercase letters x y z for anticlockwise.

There are some examples in the following picture.

As you know that a Rubik’s cube can be solved with several turnings, so we can use the letters mentioned above to represent the solution and a solution is a string containing these lowercase or capital letters. As the string may be very long, so after moving as the string, the cube may return the original status as it begins (completely the same), we define this string as a “meaningless string”.

In this question, we will give you a string, and you should check whether the string is a “meaningless string” or not.

Input: is a single line, containing a string, length is no more than 100000.

Output: Print “Yes” is after these turnings the cube can return the cases the same as it starts, otherwise print “No”.















Was prepared: Yo’ldoshboy Sultonov

Translate by: Khujaniyazova Guzal.