题目描述

在遥远的 Lu3KO5 星球上，鬼才同学被阴险狡猾的 大兵徐DD 囚禁在一座防御严密的地下堡垒中。这座堡垒是一片巨大的迷宫，由$n \times m$的格子组成，每个格子对应迷宫中的一个位置。鬼才同学被困在$(s_x, s_y)$，而堡垒的出口位于$(t_x, t_y)$。

鬼才同学原本计划通过徐DD为他偷偷挖好的地道$(p_x, p_y)$逃走，但 大兵徐DD 早就猜到了这一步，毁掉了地道并设置了重重障碍，使得整个迷宫危机四伏。在这座堡垒中，任何人只能上下左右移动一格，而障碍物则无法通过。

然而，事情出现了转机！Luke 获得了堡垒的钥匙，并且得知了鬼才同学即将逃跑的消息。他决定迅速赶往救援。然而，Luke 了解到鬼才同学会选择一条最短的路径前往地道，而他不知道的是那条地道已经被摧毁了。为了成功营救鬼才同学，Luke 必须找到一条最短路径，赶到鬼才同学即将经过的路径中的任意一点。

在这场营救行动中，“最短路径”有一个特别的定义：鬼才同学会将他每一步的移动方向编码成一个数字序列，上代表 1，右代表 2，下代表 3，左代表 4。例如，如果鬼才同学的行走方向是$上(1) \rightarrow 左(4) \rightarrow 下(3) \rightarrow 右(2)$，那么路径的编码为$1432$。在所有可能的路径中，编码数字最小的路径才被视为最短路径。

你能帮助 Luke 计算出他最少需要走多少步，才能成功在鬼才同学的行走路径中找到他并完成营救吗？

输入格式

输入共$n + 1$行。

第一行包含八个正整数$n, m, sx, sy, tx, ty, px, py$。鬼才、家门、地道所处位置互不相同，但不保证家门在家的边缘。

接下来共$n$行，每行$m$个整数，用来描述$XDD$的家的俯视图。其中第$i$行的第$j$个数表示$(i, j)$是否被设置障碍，有用 1 表示，没有用 0 表示。

输出格式

输出共一行，表示 Luke 最少需要走的步数。

若 鬼才 没有到达地道的可行路径 Luke 没有到达 鬼才 行走的路径中的任意一点的可行路径，则输出 −1。

样例输入 #1

6 6 2 2 5 5 4 4
0 0 0 0 0 0
0 0 1 0 1 0
0 1 1 0 1 0
0 0 0 0 1 0
1 1 1 1 0 0
0 0 0 0 0 0

样例输出 #1

7

样例输入 #2

4 4 2 2 3 3 4 3
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0

样例输出 #2

-1

数据范围

对于$30\%$的数据，$n, m \le 10$。

对于$100\%$的数据，$1 \le sx, tx, px \le n \le 10^3; 1 \le sy, ty, py \le m \le 10^3$。