하이퍼 토마토

시프트의 토마토 농장에는 아래 그림과 같이 토마토를 보관하는 큰 11차원 창고가 있다. 창고는 m × n × o × p × q × r × s × t × u × v × w 크기의 격자 모양이고, 각 칸에 토마토를 하나씩 보관할 수 있다.

창고에 보관된 토마토 중에는 잘 익은 것도 있지만 아직 익지 않은 토마토도 있을 수 있다. 보관 후 하루가 지나면 익은 토마토에 인접한 익지 않은 토마토는 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 $\begin{bmatrix} \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0\\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \pm 1 \end{bmatrix}$의 스물두 방향에 있는 토마토를 말한다. 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 시프트는 창고에 보관된 토마토가 며칠이 지나면 모두 익게 되는지 그 최소 일수를 알고 싶어 한다.

m, n, o, p, q, r, s, t, u, v, w와 익은 토마토, 익지 않은 토마토의 정보가 주어졌을 때, 며칠이 지나면 토마토가 모두 익는지 그 최소 일수를 구하는 프로그램을 작성하라. 창고의 일부 칸에는 토마토가 들어 있지 않을 수도 있다.

첫 줄에는 창고의 크기를 나타내는 자연수 m, n, o, p, q, r, s, t, u, v, w가 주어진다. 단, 1 ≤ mnopqrstuvw ≤ 10^6 이다.

둘째 줄부터는 창고에 저장된 토마토의 정보가 주어진다. 창고 안의 격자 공간을 (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)부터 (m, n, o, p, q, r, s, t, u, v, w)까지의 좌표로 나타낸다고 하면,

• 둘째 줄에는 (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)부터 (m, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)까지에 들어 있는 토마토 m개의 정보가 주어지고,
• 이러한 줄이 n번 반복되어 (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)부터 (m, n, 1, 1, 1, 1, 1, 1, 1, 1, 1)까지에 들어 있는 토마토 mn개의 정보가 주어지고,
• 이러한 n개의 줄이 o번 반복되어 (m, n, o, 1, 1, 1, 1, 1, 1, 1, 1)까지에 들어 있는 토마토 mno개의 정보가 주어지고,
• 이러한 no개의 줄이 p번 반복되어 (m, n, o, p, 1, 1, 1, 1, 1, 1, 1)까지에 들어 있는 토마토 mnop개의 정보가 주어지고,
• ⋯ 이와 같은 방법으로 nopqrstuvw개의 줄에 걸쳐 (m, n, o, p, q, r, s, t, u, v, w)까지에 들어 있는 토마토 mnopqrstuvw개의 정보가 모두 주어진다.

정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어 있지 않은 칸을 나타낸다.

토마토가 모두 익을 때까지 최소 며칠이 걸리는지 계산해 출력한다. 저장될 때부터 모든 토마토가 익어 있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지 못하는 상황이면 -1을 출력해야 한다.