CF676D.Theseus and labyrinth

Theseus has just arrived to Crete to fight Minotaur. He found a labyrinth that has a form of a rectangular field of size n × m and consists of blocks of size 1 × 1.

Each block of the labyrinth has a button that rotates all blocks 90 degrees clockwise. Each block rotates around its center and doesn't change its position in the labyrinth. Also, each block has some number of doors (possibly none). In one minute, Theseus can either push the button in order to rotate all the blocks 90 degrees clockwise or pass to the neighbouring block. Theseus can go from block A to some neighbouring block B only if block A has a door that leads to block B and block B has a door that leads to block A.

Theseus found an entrance to labyrinth and is now located in block (x__T, y__T) — the block in the row x__T and column y__T. Theseus know that the Minotaur is hiding in block (x__M, y__M) and wants to know the minimum number of minutes required to get there.

Theseus is a hero, not a programmer, so he asks you to help him.

忒修斯刚刚抵达克里特岛，准备与弥诺陶洛斯战斗。他发现了一座迷宫，其形状为一个 $n \times m$ 的矩形区域，由若干 $1 \times 1$ 的方块组成。

迷宫中每个方块上都装有一个按钮，按下该按钮可使所有方块绕各自中心顺时针旋转 $90^\circ$。旋转过程中，各块位置不变（即不发生平移）。此外，每个方块上开有若干扇门（也可能一扇也没有）。忒修斯每分钟可执行以下两种操作之一：

• 按下按钮，使所有方块顺时针旋转 $90^\circ$；
• 移动到一个相邻的方块。

忒修斯仅当满足如下条件时，才可从方块 $A$ 移动至相邻方块 $B$：

• 方块 $A$ 上有一扇朝向 $B$ 的门，且
• 方块 $B$ 上也有一扇朝向 $A$ 的门。

忒修斯已找到迷宫入口，当前位于方块 $(x_T, y_T)$ —— 即第 $x_T$ 行、第 $y_T$ 列的方块。他得知弥诺陶洛斯藏身于方块 $(x_M, y_M)$，现希望知道抵达该处所需的最少分钟数。

忒修斯是一位英雄，而非程序员，因此他请求你助他一臂之力。

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 1000) — the number of rows and the number of columns in labyrinth, respectively.

Each of the following n lines contains m characters, describing the blocks of the labyrinth. The possible characters are:

• «+» means this block has 4 doors (one door to each neighbouring block);
• «-» means this block has 2 doors — to the left and to the right neighbours;
• «|» means this block has 2 doors — to the top and to the bottom neighbours;
• «^» means this block has 1 door — to the top neighbour;
• «>» means this block has 1 door — to the right neighbour;
• «<» means this block has 1 door — to the left neighbour;
• «v» means this block has 1 door — to the bottom neighbour;
• «L» means this block has 3 doors — to all neighbours except left one;
• «R» means this block has 3 doors — to all neighbours except right one;
• «U» means this block has 3 doors — to all neighbours except top one;
• «D» means this block has 3 doors — to all neighbours except bottom one;
• «*» means this block is a wall and has no doors.

Left, right, top and bottom are defined from representing labyrinth as a table, where rows are numbered from 1 to n from top to bottom and columns are numbered from 1 to m from left to right.

Next line contains two integers — coordinates of the block (x__T, y__T) (1 ≤ x__T ≤ n, 1 ≤ y__T ≤ m), where Theseus is initially located.

Last line contains two integers — coordinates of the block (x__M, y__M) (1 ≤ x__M ≤ n, 1 ≤ y__M ≤ m), where Minotaur hides.

It's guaranteed that both the block where Theseus starts and the block where Minotaur is hiding have at least one door. Theseus and Minotaur may be initially located at the same block.

输入的第一行包含两个整数 $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$。

下一行包含两个整数——起始格子的坐标 $(x_T, y_T)$（$1 ≤ x_T ≤ n$, $1 ≤ y_T ≤ m$），即忒修斯（Theseus）初始所在位置。

最后一行包含两个整数——目标格子的坐标 $(x_M, y_M)$（$1 ≤ x_M ≤ n$, $1 ≤ y_M ≤ m$），即弥诺陶洛斯（Minotaur）藏身的位置。

保证忒修斯起始位置与弥诺陶洛斯藏身位置的格子均至少有一扇门。忒修斯与弥诺陶洛斯可能初始位于同一格子。

If Theseus is not able to get to Minotaur, then print -1 in the only line of the output. Otherwise, print the minimum number of minutes required to get to the block where Minotaur is hiding.

如果忒修斯无法到达弥诺陶洛斯，则在输出的唯一一行中打印 -1。否则，打印到达弥诺陶洛斯藏身方块所需的最少分钟数。

Assume that Theseus starts at the block (x__T, y__T) at the moment 0.

假设忒修斯在时刻 0 从方块 $(x_T, y_T)$ 出发。