Escape the Maze

Little Ming is playing a maze game. The maze is a 2D grid composed of \(N \times N\) cells. His starting position is at the top‐left cell and he needs to reach the bottom‐right cell to exit the maze.

Each step, he can move to one of the four adjacent cells (up, down, left, right), provided that the target cell is accessible.

The maze contains three types of cells:

• . represents an empty cell that Ming can go through;
• # represents a wall that Ming cannot pass;
• X represents a trap. Ming can only step on a trap if he is in the invincible state.

Additionally, there are invincibility power‐up cells marked by %. When Ming lands on such a cell for the first time, he automatically obtains invincibility which will last for \(K\) steps. If he visits the same invincible cell again, he will not get the power‐up a second time.

While he is invincible, Ming can safely pass through trap cells (X). Note that stepping onto a power-up cell resets his invincibility count to \(K\) if it is his first visit to that cell.

Your task is to compute the minimum number of steps Ming needs to exit the maze. If it is impossible for him to exit, output -1.

inputFormat

The first line contains two integers \(N\) and \(K\), where \(N\) is the size of the maze (number of rows/columns) and \(K\) is the number of steps the invincibility lasts.

The following \(N\) lines each contain a string of length \(N\) describing the maze. The characters can be:

• . (an empty cell),
• # (a wall),
• X (a trap), or
• % (an invincibility power‐up cell).

outputFormat

Output a single integer representing the minimum number of steps required for Ming to exit the maze. If it is impossible to exit, output -1.

sample

3 3
...
.%.
...

4