Crate label search

Find where a word is written in a grid of crate labels.

A warehouse wall holds crates in a rectangular grid; each crate carries one lowercase letter. grid is a list of equal-length strings, one per row, row 0 at the top. A word is present if it can be read in a straight line of consecutive crates in one of four directions (diagonals do not count):

• "R": to the right (increasing column)
• "D": downward (increasing row)
• "L": to the left (decreasing column)
• "U": upward (decreasing row)

The start of a reading is the crate holding the word's first letter, wherever the line ends up (so a word read leftwards starts at its right-hand end). A word of one letter is present at every crate with that letter.

Among all the places the word is present, report the one whose start comes first in reading order: smallest row, then smallest column. If several directions work from that same start, prefer them in the order R, D, L, U.

Input: grid, a list of strings, and word, a string.

Output: a list [row, column, direction] with 0-based row and column and the direction letter as a string, or [] if the word is nowhere in the grid.