The Alphabetical Route Through the Letter Maze

A puzzle maze is a grid of letters board, given as m strings of length n. A walker starts on the top-left cell and must reach the bottom-right cell, moving only right or down one cell at a time. The letters of the cells visited, in order (both ends included), spell a word of length m + n - 1.

Return the word that comes first in alphabetical (lexicographic) order among all possible routes.

Examples

Input:  board = ["aaz", "azz", "baa"]
Output: "aabaa"
Explanation: going right first gives "aaz..." at best; going down first
reaches "aab", then "aa".

Input:  board = ["dcb"]
Output: "dcb"

Input:  board = ["ab", "ba"]
Output: "aba"

Constraints

• 1 <= m, n and m * n <= 4 * 10**5
• All strings have length n and contain lowercase letters only.
• Listing every route is hopeless: a 20 x 20 board already has over 35 billion of them.

Goals

• Build a lexicographically smallest string one letter at a time
• Sweep a grid by anti-diagonals, keeping every cell that is still tied for the best prefix
• See why breaking ties arbitrarily can walk into a dead end