Many thousand years ago, stories of a man, known as Ben-10's lost brother, got spread throughout the world. Legend says that he, whose name is Beza-10, was a very peculiar guy, with jaw-dropping abilities and powers. Due to that, Ben-10 got afraid that his brother would become more famous and powerful than him, so he decided to banish Beza from the dimension we live in.
Years passed, and now Beza is planning his return, so he can finally get the revenge he wanted ever since he was banned. However, travelling on different dimensions is not as simple as he thought it would be, therefore, he needs your help.
Beza-10 is trapped on a dimension represented as a $$$N$$$x$$$M$$$ grid. Because the spell cast on him was so powerful, the grid got filled with many traps, denoted by the character #, on which he can't step on, because if he did, he would suffer tremendous pain and probably die. Therefore, he can only walk on empty spaces.
Just like Ben-10, Beza possesses a magical watch, which is capable of shapeshifting him into powerful forms. However, as he is on an unknown dimension, his watch no longer works as expected: he can only shapeshift into chess pieces, except the pawn. After shapeshifting into a chosen chess piece, he will move according to the rules of this specific piece, which are just like in normal chess:
Also, Beza is scared that the excessive use of his watch will break it, and, therefore, decided that he will use it at most $$$K$$$ times.
Initially, assume that Beza has the form of the king chess piece, is located on the position of the grid that contains the character 'B', and wishes to reach the escape portal, marked with a 'P' on the grid. He asks you what is the minimum number of movements he will require in order to escape, doing at most $$$K$$$ shapeshifts, or report that it is impossible.
The first line of input has three integers: $$$N$$$ and $$$M$$$ ($$$2 \le N, M \le 100$$$), the grid dimensions, and $$$K$$$ ($$$0 \le K \le 100$$$), which is the maximum amount of shapeshifts Beza is willing to do. The next $$$N$$$ lines contain $$$M$$$ characters each, which can be: a 'B', denoting the starting position of Beza-10, a 'P', the position of the escape portal, a '#', which is a trap, or a single dot $$$.$$$, which is a free space that Beza can step on.
The output consists of a single integer, which is the minimum number of movements needed to reach the portal, doing at most $$$K$$$ shapeshifts. If it is not possible to reach the portal with the given grid and conditions, print $$$"$$$-1$$$"$$$ (without quotes).
3 3 3 B.. .## .#P
2
7 5 3 B..#. .#..# #...# ..... .#.#. #.#.# ..P..
3