You're a mikemon breeder currently in the middle of your journey to become a mikemon master. Your current obstacle is go through the infamous Biridian Forest. The forest The Biridian Forest is a two-dimensional grid consisting of r rows and c columns. Each cell in Biridian Forest may contain a tree, or may be vacant. A vacant cell may be occupied by zero or more mikemon breeders (there may also be breeders other than you in the forest). Mikemon breeders (including you) cannot enter cells with trees. One of the cells is designated as the exit cell. The initial grid, including your initial position, the exit cell, and the initial positions of all other breeders, will be given to you. Here's an example of such grid (from the first example): Moves Breeders (including you) may move in the forest. In a single move, breeders may perform one of the following actions: Do nothing. Move from the current cell to one of the four adjacent cells (two cells are adjacent if they share a side). Note that breeders cannot enter cells with trees. If you are located on the exit cell, you may leave the forest. Only you can perform this move — all other mikemon breeders will never leave the forest by using this type of movement. After each time you make a single move, each of the other breeders simultaneously make a single move (the choice of which move to make may be different for each of the breeders). Mikemon battle If you and t ( t > 0) mikemon breeders are located on the same cell, exactly t mikemon battles will ensue that time (since you will be battling each of those t breeders once). After the battle, all of those t breeders will leave the forest to heal their respective mikemons. Note that the moment you leave the forest, no more mikemon battles can ensue, even if another mikemon breeder move to the exit cell immediately after that. Also note that a battle only happens between you and another breeders — there will be no battle between two other breeders (there may be mul