忒修斯刚刚抵达克里特岛与牛头怪战斗。他发现了一个迷宫,其形状为 n × m 的矩形区域,由大小为 1 × 1 的块组成。
迷宫的每个方块都有一个按钮,可以将所有方块顺时针旋转 90 度。每个方块都围绕其中心旋转,并且不会改变其在迷宫中的位置。此外,每个街区都有一定数量的门(可能没有)。一分钟内,忒修斯可以按下按钮使所有方块顺时针旋转 90 度,也可以传递到相邻的方块。仅当 A 块有通往 B 块的门且 B 块有通往 A 块的门时,忒修斯才能从 A 块到某个邻近的 B 块。
忒修斯找到了迷宫的入口,现在位于块 (xT, yT)——xT 行和 yT 列的块中。忒修斯知道牛头怪藏在块 (xM, yM) 中,并且想知道到达那里所需的最少分钟数。
These修斯是英雄,不是程序员,所以他请求你帮助他。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1000) - 分别是迷宫中的行数和列数。
接下来的n行每行包含m个字符,描述迷宫的方块。可能的字符有:
- «+» 表示该街区有 4 扇门(每个相邻街区一扇门);
- «-» 表示该街区有 2 扇门 — 向左和向右邻居;
- «|»意味着这个街区有 2 个门——通向顶部和底部的邻居;
- «^» 表示该块有 1 扇门 — 通向最上面的邻居;
- «>» 表示该街区有 1 扇门 — 通向右侧邻居;
- «<» 表示该街区有 1 扇门 — 通往左侧邻居;
- «v» 表示该街区有 1 扇门 — 通往底部邻居;
- «L» 表示该街区有 3 扇门 — 通往除左边一扇之外的所有邻居;
- «R» 表示该街区有 3 扇门 — 通往除右边一扇之外的所有邻居;
- «U» 表示该街区有 3 扇门 — 通往除顶部一扇之外的所有邻居;
- «D» 表示该街区有 3 扇门 — 通往除底部一扇之外的所有邻居;
- «*» 表示该街区是一堵墙并且没有门。
左、右、上、下的定义是将迷宫表示为一个表格,其中行从上到下编号为 1 到 n,列从左到右编号为 1 到 m。
下一行包含两个整数 - 块的坐标 (xT, yT) (1 ≤ xT ≤ n, 1 ≤ yT ≤ m),这是Theseus 最初所在的位置。
最后一行包含两个整数 - 牛头怪隐藏的方块坐标 (xM, yM) (1 ≤ xM ≤ n, 1 ≤ yM ≤ m)。
保证忒修斯开始的方块和牛头怪躲藏的方块都至少有一扇门。忒修斯和牛头怪最初可能位于同一个街区。
输出
如果Theseus 无法到达 Minotaur,则在输出的唯一行中打印 -1。否则,打印到达牛头怪隐藏的区块所需的最少分钟数。
示例
输入 #1
2 2 +* *U 1 1 2 2
输出 #1
-1
输入 #2
2 3 <>< ><> 1 1 2 1
输出 #2
4
注意
假设Theseus 从时刻 0 的块 (xT, yT) 开始。