Maze Path with Letter Sequence Constraint

You are given a maze consisting of N × M grid cells, where each cell is filled with either letter \(A\) or \(B\). You start at the top‐left cell and your goal is to reach the bottom‐right cell. At each move you can travel to an adjacent cell (up, down, left, or right).

However, due to a special constraint, the sequence of letters along your path must follow an alternating pattern: first you must traverse exactly \(K\) cells containing letter \(A\), then exactly \(K\) cells containing letter \(B\), then exactly \(K\) cells \(A\), then \(K\) cells \(B\), and so on. Note that only complete groups except possibly the last group are required to contain exactly \(K\) cells; the final group (either of \(A\) or \(B\)) may be incomplete. It is guaranteed that the starting cell is an \(A\), so the first group corresponds to \(A\) cells.

Your task is to compute the minimum number of steps required for the path satisfying these constraints. If there is no valid path that meets the requirements, output -1.

Note: The number of visited cells in the path does not necessarily need to be a multiple of \(K\) because the last group may contain fewer than \(K\) cells.

For example, when \(K = 3\), the following routes are valid (each letter represents a visited cell in order):

AA
AAAB
AAABBBAAABBB

While these routes are not valid:

ABABAB
ABBBAAABBB
AAABBBBBBAAA

inputFormat

The first line contains three integers \(N\), \(M\) and \(K\) separated by spaces.

The next \(N\) lines each contain a string of length \(M\) consisting only of the characters 'A' and 'B', representing the maze.

outputFormat

Output a single integer representing the minimum number of steps required to reach the bottom‐right cell following the letter sequence constraint. If no valid path exists, output -1.

sample

1 1 3
A

0