在遥远的 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。
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
7
4 4 2 2 3 3 4 3 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0
-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。