Tomatoes

Cheolsu's tomato farm has a large warehouse for storing tomatoes. As shown in the figure below, each tomato is placed one per cell of a grid-shaped box, and the boxes are then stacked vertically in the warehouse.

Among the stored tomatoes, some are already ripe while others are not yet ripe. One day after storage, the unripe tomatoes adjacent to a ripe tomato become ripe under its influence. A cell adjacent to a tomato means a tomato in one of the six directions: up, down, left, right, front, and back. Tomatoes in diagonal directions are not affected, and a tomato never ripens on its own.

Given the size of the grid boxes and the information about which tomatoes are ripe and which are not, write a program that determines the minimum number of days until all the stored tomatoes become ripe. Note that some cells of a box may contain no tomato.

The first line contains two integers $M$ and $N$ describing the size of a box, and an integer $H$ describing the number of stacked boxes. Here $M$ is the number of columns and $N$ is the number of rows of a box, with $2 \le M \le 100$, $2 \le N \le 100$, and $1 \le H \le 100$.

Starting from the second line, the information of the stored tomatoes is given from the bottom box up to the top box. That is, each box is described by $N$ lines, and each line contains $M$ integers describing the state of the tomatoes in that row. The integer $1$ denotes a ripe tomato, $0$ denotes an unripe tomato, and $-1$ denotes an empty cell with no tomato. Such a block of $N$ lines is repeated $H$ times, from the bottom box to the top box.

The input always contains at least one tomato.

Print the minimum number of days until all the tomatoes are ripe. If all the tomatoes are already ripe at the time of storage, print $0$; if the tomatoes can never all ripen, print $-1$.