A. The Fault in Our Cubes

time limit per test

0.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Rula is the Human Resources Manager at Mixed Dimensions Inc. She has some very delightful puzzles for the employees to enjoy their free time at the office. One of these puzzles is the Worm Puzzle.

The puzzle consists of 27 cubic pieces of several types. The pieces are connected by a rope that runs through holes in the pieces, and allows the pieces to rotate. In order to solve the puzzle, you need to build a 3x3x3 cube.

Each piece has one of the following three types:

• Type E represents an end cube, it has a hole at one face only. This piece is always connected to only one other piece.
• Type I represents a cube which has two holes on opposite faces, the rope goes straight into one hole and out through the other.
• Type L represents a cube which has two holes in two adjacent faces, the rope enters through one face, makes a 90 degree turn, and exits through the other face.

Well, Hasan has cut the rope of the puzzle by mistake, of course he didn’t want to tell Rula about it, so he bought a new rope and linked the pieces together to make a new Worm Puzzle, but he wasn't sure whether he linked them in their original order or not.

Now Rula has been trying to solve the puzzle for two days, but with no success, although she used to solve it in 30 seconds. She started to suspect that something might be wrong with the puzzle.

She asked one of the engineers at Mixed Dimensions to verify whether the puzzle is solvable or not. Unfortunately, that engineer was Hasan, and of course, the question is difficult for him to answer.

Given the type of each piece, and the order in which Hasan linked the pieces together, can you help him by finding whether the given puzzle is solvable or not?

Input

The input consists of a string of 27 letters, each letter will be either an E, I, or L, which represents the type of that piece.

The first and last letters are always E.

Output

Print YES if the given puzzle is solvable, otherwise print NO.

Examples

input

EILILLLLLLILILLLLLLILILLLLE

output

YES

input

EILLLILLILLLILILLLLILILILIE

output

YES

input

EILLILLLILLILLLILLLILLLLILE

output

NO

思路：暴力dfs即可。

# include 
    
     # include 
     
      # include 
      
       using namespace std;int fx[6] = {1, -1, 0, 0, 0, 0};int fy[6] = {0, 0, 1, -1, 0, 0};int fz[6] = {0, 0, 0, 0, 1, -1};char s[30];int vis[4][4][4];bool judge(int x, int y, int z){    if(x<0||x>2||y<0||y>2||z<0||z>2||vis[x][y][z])        return false;    return true;}bool dfs(int x ,int y, int z, int icount, int pos){    char c = s[icount];    int px = x + fx[pos];    int py = y + fy[pos];    int pz = z + fz[pos];    if(icount == 27)        return judge(px, py, pz);    if(!judge(px, py, pz))        return false;    if(c == 'I')    {        vis[px][py][pz] = 1;        if(dfs(px, py, pz, icount+1, pos))            return true;        else        {            vis[px][py][pz] = 0;            return false;        }    }    else if(c == 'L')    {        vis[px][py][pz] = 1;        for(int i=0; i<6; ++i)        {            if(i != pos)            {                if(dfs(px, py, pz, icount+1, i))                    return true;            }        }        vis[px][py][pz] = 0;        return false;    }}int main(){    while(~scanf("%s",s+1))    {        memset(vis, 0, sizeof(vis));        bool flag = false;        for(int i=2; i<27; ++i)            if(s[i]=='E')            {                flag = true;                break;            }        if(flag)        {            puts("NO");            continue;        }        for(int i=0; i<3; ++i)        {            for(int j=0; j<3; ++j)            {                for(int k=0; k<3; ++k)                {                    vis[i][j][k] = 1;                    if(dfs(i, j, k, 2, 0))                    {                        flag = true;                        break;                    }                    vis[i][j][k] = 0;                }                if(flag)                    break;            }            if(flag)                break;        }        if(flag)            puts("YES");        else            puts("NO");    }    return 0;}