Spell a word on a 5-column letter board

A text-entry device shows the 26 lowercase letters on a board 5 columns wide, filled row by row. Letter c sits at row (ord(c) - ord('a')) // 5 and column (ord(c) - ord('a')) % 5:

    0 1 2 3 4
0   a b c d e
1   f g h i j
2   k l m n o
3   p q r s t
4   u v w x y
5   z

The last row holds only z. The cells to its right do not exist, and the cursor may never move onto them or off the board.

The cursor starts on a at (0, 0). It accepts five commands:

• U, D, L, R: move one cell up, down, left or right.
• !: select the letter under the cursor.

Implement word_path(word: str) -> str. It returns a command string that types word using the fewest possible moves. Any shortest answer is accepted.

Constraints

• 0 <= len(word) <= 100
• word contains only lowercase English letters.

Example 1

word_path("bad")  ->  "R!L!RRR!"

Move right to b and select it, move left to a and select it, then move right three cells to d.

Example 2

word_path("oz")  ->  "DDRRRR!LLLLDDD!"

o is at (2, 4). To reach z the cursor must move left to column 0 before it moves down. Moving down first would step onto a missing cell in row 5.