The Blinking Glass Walkway

A museum walkway is the grid grid (a list of equal-length strings) with a cycle length k:

• 'S' is your start (exactly one) and 'X' is the exit (exactly one); both, like '.', are always safe to stand on. '#' is a wall;
• a digit 'd' is a glass panel that is solid only during minutes t with t % k == d. At every other minute it is retracted and you may not be on it.

You stand on S at minute 0. Every minute you either stay where you are or move one cell up, down, left or right; afterwards it is minute t + 1, and the cell you are on must be safe at that minute. Return the earliest minute at which you can stand on X, or -1 if that never happens.

Examples

Input:  grid = ["S20",
                ".#X"], k = 3
Output: 4
Explanation: wait on S for minute 1, step onto panel 2 at minute 2, onto panel 0 at minute 3,
             and down to X at minute 4.

Input:  grid = ["S21X"], k = 3
Output: -1
Explanation: you can only be on panel 2 at minutes 2, 5, 8, ... and the next minute is never
             one where panel 1 is solid.

Input:  grid = ["S0X"], k = 1
Output: 2

Constraints

• 1 <= rows, cols <= 50, rows * cols >= 2, 1 <= k <= 10.
• Every digit in the grid is smaller than k.

Goals

• Add the time modulo the cycle length to the BFS state
• Model waiting in place as a move
• Explain why (cell, t mod k) is enough to finish on unreachable maps