Problem Description

总教头的助手被阴险狡猾的 WA将军 囚禁在一座防御严密的地下堡垒中。这座堡垒是一片巨大的迷宫，由$n \times m$的格子组成，每个格子对应迷宫中的一个位置。小助手 被困在$(s_x, s_y)$，而堡垒的出口位于$(t_x, t_y)$。

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

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

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

你能帮助 AC队长 计算出他最少需要走多少步，才能成功在 小助手 的行走路径中找到他并完成营救吗？

Input Format

输入共$n + 1$行。

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

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

Output Format

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

若 小助手 没有到达地道的可行路径

AC队长 没有到达 小助手 行走的路径中的任意一点的可行路径，则输出 −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

Hint

数据范围

对于$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$。