Taco: Reach Destination in Exactly k Steps

You are given an m x n grid representing a field, where each cell is either empty or blocked by an obstacle. The grid is represented by m strings of length n where a . denotes an empty cell and a # denotes an obstacle.

Your task is to determine whether it is possible to move from the top-left cell at \((0,0)\) to the bottom-right cell at \((m-1, n-1)\) in exactly k steps. You may move one step at a time in any of the four cardinal directions (up, down, left, or right).

Note: The move count must be exactly k when you reach the destination for the answer to be POSSIBLE. Otherwise, output IMPOSSIBLE.

inputFormat

The first line of input contains three integers m, n and k separated by spaces, where m is the number of rows and n is the number of columns in the grid, and k is the exact number of steps you must take.

This is followed by m lines, each containing a string of length n that represents a row of the grid.

outputFormat

Output a single line: POSSIBLE if it is possible to reach the destination in exactly k steps, and IMPOSSIBLE otherwise.

3 3 4
...
.#.
...

POSSIBLE