J. Power-up Maze
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

BB-8 is rolling through a maze, represented by a 2D grid with $$$r$$$ rows and $$$c$$$ columns. The grid is comprised of five different characters. "#" represents a wall, and "." represents an empty tile. "P" is a powerup for BB-8, "A" is BB-8's starting point, and "B" is the destination point for it to reach. BB-8 can freely pass through empty tiles, powerups, and its starting and destination points, but cannot travel through walls.

Each second, BB-8 can make a number of moves equal to its power, which starts at $$$1$$$. BB-8 can only move orthogonally through the grid; in other words, it can move one tile up, down, left, or right with a single movement action. It starts on the space marked A and wants to move to the space marked B.

Around the maze are $$$p$$$ powerups marked P. BB-8 must collect every powerup to complete the maze. Whenever it moves over a powerup, it can choose to collect the powerup to increase its power by $$$1$$$, which means it can make up to $$$1$$$ more moves in subsequent seconds. When a powerup is collected, BB-8's current second ends and the space it was on becomes an empty tile so that the powerup cannot be collected again.

Given a maze, determine the least amount of seconds BB-8 can take to reach point "B", starting from point "A", and collecting every powerup.

Input

The first line contains three integers $$$r$$$, $$$c$$$, and $$$p$$$ $$$(4 \le r, c \le 100; \: 0 \le p \le 12)$$$ — the number of rows, columns, and powerups in the grid.

The next $$$r$$$ lines each contain a string of length $$$c$$$ which describes the 2D grid, as explained above.

The perimeter of the grid (first and last rows and columns) are always walls "#".

There is exactly one "A", one "B", and $$$p$$$ "P"s in every maze.

Output

Output a single integer: the minimum number of seconds it takes for BB-8 to reach the destination "B" after collecting every powerup. In the case where BB-8 cannot reach "B" from "A" or it cannot collect all the powerups, output IMPOSSIBLE instead.

Examples
Input
5 7 3
#######
#P....#
#.AP#B#
#P..###
#######
Output
5
Input
4 5 2
#####
#AB##
#P#P#
#####
Output
IMPOSSIBLE
Input
4 6 5
######
#APPB#
#PPP.#
######
Output
6
Note

A possible sequence of moves BB-8 can make is shown for the first test case.

1. One tile left.

2. One tile up, and collect a powerup.

3. Two tiles down, and collect a powerup.

4. Two tiles right and one tile up, and collect a powerup.

5. One tile up, two tiles right, and one tile down to get to the destination.