Codeforces 3A

A. Shortest path of the king

time limit per test

1 second

memory limit per test

64 megabytes

input

standard input

output

standard output

The king is left alone on the chessboard. In spite of this loneliness, he doesn't lose heart, because he has business of national importance. For example, he has to pay an official visit to square t. As the king is not in habit of wasting his time, he wants to get from his current position s to square t in the least number of moves. Help him to do this.

In one move the king can get to the square that has a common side or a common vertex with the square the king is currently in (generally there are 8 different squares he can move to).

Input

The first line contains the chessboard coordinates of square s, the second line — of square t.

Chessboard coordinates consist of two characters, the first one is a lowercase Latin letter (from a to h), the second one is a digit from 1to 8.

Output

In the first line print n — minimum number of the king's moves. Then in n lines print the moves themselves. Each move is described with one of the 8: L, R, U, D, LU, LD, RU or RD.

L, R, U, D stand respectively for moves left, right, up and down (according to the picture), and 2-letter combinations stand for diagonal moves. If the answer is not unique, print any of them.

Examples

input

a8
h1

output

7
RD
RD
RD
RD
RD
RD
RD

题意：给出两个king棋子在国际象棋棋盘中的位置（棋盘见题目描述中的图），king每次可以从八个方向中选取一个走一步，问第一个king至少走几步能走到第二个king的位置。输出最少的步数和走的方向。

题解：模拟。其实这题本可以用BFS做，但是懒得打BFS了，直接模拟出了答案。。。

　　　考虑一下，其实最少走的步数就是两个棋子横纵坐标之差的较大值，然后走的方向与两个棋子本身的相对方向有关，具体讨论参见代码，思路是非常显而易见的。。。

#include<bits/stdc++.h>
using namespace std;
int x,y,p,q,Min,Max;
char s[5];
int main()
{
    scanf("%s",s);
    x=s[0]-'a'+1;
    y=s[1]-'0';
    scanf("%s",s);
    p=s[0]-'a'+1;
    q=s[1]-'0';
    Min=min(abs(x-p),abs(y-q));
    Max=max(abs(x-p),abs(y-q));
    printf("%d
",Max);
    if (Min==abs(x-p))
    {
        if (x<=p&&y<=q)
        {
            for (int i=1;i<=Min;++i)
            printf("RU
");
            for (int i=Min+1;i<=Max;++i)
            printf("U
");
        }
        if (x<=p&&y>q)
        {
            for (int i=1;i<=Min;++i)
            printf("RD
");
            for (int i=Min+1;i<=Max;++i)
            printf("D
");
        }
        if (x>p&&y<=q)
        {
            for (int i=1;i<=Min;++i)
            printf("LU
");
            for (int i=Min+1;i<=Max;++i)
            printf("U
");
        }
        if (x>p&&y>q)
        {
            for (int i=1;i<=Min;++i)
            printf("LD
");
            for (int i=Min+1;i<=Max;++i)
            printf("D
");
        }
    }
    else if (Min==abs(y-q))
    {
        if (x<=p&&y<=q)
        {
            for (int i=1;i<=Min;++i)
            printf("RU
");
            for (int i=Min+1;i<=Max;++i)
            printf("R
");
        }
        if (x<=p&&y>q)
        {
            for (int i=1;i<=Min;++i)
            printf("RD
");
            for (int i=Min+1;i<=Max;++i)
            printf("R
");
        }
        if (x>p&&y<=q)
        {
            for (int i=1;i<=Min;++i)
            printf("LU
");
            for (int i=Min+1;i<=Max;++i)
            printf("L
");
        }
        if (x>p&&y>q)
        {
            for (int i=1;i<=Min;++i)
            printf("LD
");
            for (int i=Min+1;i<=Max;++i)
            printf("L
");
        } 
    }
    return 0;
}