Problem: 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.

<image>

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 1 to 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

Solution (in PYTHON3):

Solution:

def shortestPath():
       #citim datele de intrare
       kingPosition = input()
       destination = input()
       #definim marimea bordului
       boardSize = 8
       #initializam o lista bidimensionala cu toate elementele -1
       chessBoard = [[-1 for x in range(boardSize)] for y in range(boardSize)]
       #gasim pozitia regelui, deoarece incepem sa numaram de la 0, scadem unu
       kingRow = int(kingPosition[1])-1
       #a doua coordonata a pozitiei e data ca caracter, de aceea scadeam din ea ordinea in ASCII a characterului a, si vom obtine indexul
       kingColumn = ord(kingPosition[0])-ord('a')

       #verificam daca pozitia curenta este aceeasi cu pozitia destinatiei, daca da, printam ca avem nevoie de 0 pasi si iesim din functie
       if kingPosition == destination:
              print(0)
              return 
       #marcam pozitia regelui cu 0
       chessBoard[kingRow][kingColumn] = 0
       #marcam pozitia destinatiei cu -2
       chessBoard[int(destination[1])-1][ord(destination[0])-ord('a')] = -2

       #initializam o lista care va tine minte toti vecinii care trebuie de parcurs
       newNeighbors = []
       #chemam functia fillChessBoard, care v-a chimba valorile de -1 cu valori ale distantei
       #si va adauga in lista newNeighbors definita mai sus vecinii noi aparuti
       fillChessBoard(kingRow,kingColumn,chessBoard,newNeighbors)
       #atata timp cat mai avem vecini care trebuie de parcurs
       while len(newNeighbors) > 0:
              #chemam functia pentru fillChessBoard pentru fiecare din ei
              fillChessBoard(newNeighbors[0][0], newNeighbors[0][1],chessBoard,newNeighbors)
              #o data ce i-am cercetat vecinii, il stergem din list
              newNeighbors.remove(newNeighbors[0])
       #initializam lista path, care la moment tine minte doar pozitia destinatiei
       path=[[int(destination[1])-1,ord(destination[0])-ord('a')] ]
       #incepand cu pozitia destinatiei, cautam prin vecinii lui cea mai mica distanta si o adaugam in lista path
       path.append(findSmallestNeighbor([int(destination[1])-1,ord(destination[0])-ord('a')],chessBoard))
       #atat timp cat valoarea din chessBoard de pe ultima pozitie din path, nu este 0, inseamna ca nu am ajuns la pozitia regelui, deci mai cautam
       while chessBoard[path[len(path)-1][0]][path[len(path)-1][1]] != 0:
              #adaugam in lista path noi distante(cele mai mici)
              path.append(findSmallestNeighbor(path[len(path)-1],chessBoard))
       #definim lista care ne v-a ajuta sa gasim vecinii
       allNeighbors = [[1,1],[1,0],[1,-1],[0,-1],[-1,-1],[-1,0],[-1,1],[0,1]]
       #variabila i o initializam cu lungimea lui path -1 , deoarce intre 2 pozitii din path e o miscare, daca avem n pozitii, o sa avem n-1 miscari
       i = len(path)-1
       #printam nr de miscari
       print(i)
       #atata timp cat mai avem miscari pe care nu le-am analizat
       while i > 0:
              #parcurgem fiecare vecin
              for neighbor in allNeighbors:
                     #verificam in ce directe din cele 8 pozibile trebuie sa mearga regele ca sa urmeze calea spre destinatie
                     #si printam combinatia corespunzatoare de litere pentru fiecare directie
                     if path[i][0] + neighbor[0] == path[i-1][0] and path[i][1] + neighbor[1] == path[i-1][1]:
                            if neighbor == [1,1]:
                                   print('RU')
                            elif neighbor == [1,0]:
                                   print('U')
                            elif neighbor == [1,-1]:
                                   print('LU')
                            elif neighbor == [0,-1]:
                                   print('L')
                            elif neighbor == [-1,-1]:
                                   print('LD')
                            elif neighbor == [-1,0]:
                                   print('D')
                            elif neighbor == [-1,1]:
                                   print('RD')
                            elif neighbor == [0,1]:
                                   print('R')
              #decrementam i
              i -= 1

#analizeaza vecinii din urul punctului [startRow, startColumn], daca eacestia au -1 ii initializeaza cu valoarea distantei de la rege 
def fillChessBoard(startRow, startColumn, chessBoard, newNeighbors):
       allNeighbors = [[1,1],[1,0],[1,-1],[0,-1],[-1,-1],[-1,0],[-1,1],[0,1]]
       #parcurgem toti vecinii
       for neighbor in allNeighbors:
              #verificam daca nu depasim dimensiunile listei incercand sa gasim vecini si verificam daca valoarea vecinului e -1
              if startRow + neighbor[0] < len(chessBoard) and startColumn + neighbor[1] < len(chessBoard) and startRow + neighbor[0] >= 0 and startColumn + neighbor[1] >= 0 and chessBoard[startRow + neighbor[0]][startColumn + neighbor[1]] == -1:
                     #setam valoarea vecinului cu valoarea distantei fata de rege
                     chessBoard[startRow + neighbor[0]][startColumn + neighbor[1]] = chessBoard[startRow][startColumn] + 1
                     #includem vecinul in lista celor care urmeaza sa fie cercetati
                     newNeighbors.append([startRow + neighbor[0],startColumn + neighbor[1]])

#gaseste vecinul cu cea mai mica distanta pana la rege
def findSmallestNeighbor(current,chessBoard):
       allNeighbors = [[1,1],[1,0],[1,-1],[0,-1],[-1,-1],[-1,0],[-1,1],[0,1]]
       #initializam valoarea minima cu 8 pentru ca stim ca mai sau egala cu 8 distanta nu exista
       minValue = 8
       #parcurgem vecinii
       for neighbor in allNeighbors:
              #verificam daca nu am depasit limita listei incercand sa gasim vecini si verificam daca valoarea vecinului e mai mica decat valoarea minima
              if current[0] + neighbor[0] < len(chessBoard) and current[1] + neighbor[1] < len(chessBoard) and current[0] + neighbor[0] >= 0 and current[1] + neighbor[1] >= 0 and chessBoard[current[0]+neighbor[0]][current[1]+neighbor[1]] < minValue and chessBoard[current[0]+neighbor[0]][current[1]+neighbor[1]] != -2:
                     #valoarea minima devine valoarea vecinului cu cea mai mica valoare
                     minValue =  chessBoard[current[0]+neighbor[0]][current[1]+neighbor[1]] 
                     #salvam coordonatele vecinului cu cea mai mica valoare
                     minNeighbor = [current[0]+neighbor[0],current[1]+neighbor[1]]
       #returnam coordonatele vecinului cu cea mai mica valoare
       return minNeighbor

#chemam functia care v-a gasim cea mai scurta cale de la rege la destinatie
shortestPath()