Problem Description

Given an $n \times n \times n$ cube, it is divided into $n^3$ unit cubes, and some of the unit cubes are obstacles and cannot be passed through.

Given the coordinates of the start and the target, in each step you can move from one unit cube to an adjacent (sharing a face) non-obstacle unit cube. Find the minimum number of steps needed to go from the start to the target.

Input Format

The first line contains an integer $n$.

The next line contains $3$ integers $x_s, y_s, z_s$, representing the starting position.

The next line contains $3$ integers $x_t, y_t, z_t$, representing the target position.

Then $n$ $n \times n$ $01$ matrices are given. In the $i$-th layer, the cell in row $j$ and column $k$ indicates whether $(j, k, i)$ is an obstacle ($1$ means obstacle).

It is guaranteed that the start and the target positions are not obstacles.

Output Format

Output one integer in a single line, representing the minimum number of steps. If it is impossible to reach, output $-1$.

2
1 1 1
1 1 2
00
10
01
00

1

3
2 3 1
1 1 1
000
010
000
111
111
111
111
111
111

3

3
2 1 1
3 2 2
000
010
110
010
001
001
101
110
000

3

Hint

Constraints

For all testdata, $1 \le n \le 100$.

Translated by ChatGPT 5