Grid Item Movement

In this problem, you are given a grid with dimensions (n \times m) where each cell contains either a capital letter (A-Z), its corresponding lowercase letter (a-z) representing its target position, a dot ('.'), or a star ('*'). For every uppercase letter found in the grid, there is exactly one corresponding lowercase letter which denotes the destination for that letter. Your task is to generate a sequence of moves that will move each item from its initial position to its target position.

Each move must be in one of the four directions: UP, DOWN, LEFT, or RIGHT. A move is represented by a line in the format: X DIRECTION, where X is the uppercase letter being moved.

The movement follows the Manhattan distance and is performed by first adjusting the row coordinate and then the column coordinate. Mathematically, if an item starts at ((x_i,y_i)) and must reach ((x_t,y_t)), then the number of moves required is (|x_t - x_i| + |y_t - y_i|) with appropriate steps in the vertical and horizontal directions.

inputFormat

The first line contains two integers (n) and (m) (the number of rows and columns of the grid). The next (n) lines each contain a string of length (m) representing the grid. It is guaranteed that for every uppercase letter, there is a corresponding lowercase letter that denotes its target position.

outputFormat

Output a sequence of moves, one per line, that moves each item from its initial position to its target position. Each move is formatted as X DIRECTION where X is the uppercase letter and DIRECTION is one of: UP, DOWN, LEFT, or RIGHT. If no moves are needed, output an empty string.## sample

5 5
A..*.
.....
.....
.*...
...a.

A DOWN
A DOWN
A DOWN
A DOWN
A RIGHT
A RIGHT
A RIGHT