Escape the Ghost House

Seokjun has decided to visit an amusement park after a long time. Here is the conversation he had with his friends.

• Friend A: Isn't the ghost house too scary? Let's just ride the roller coaster...
• Seokjun: Come on~ What's scary about a ghost house? There's no line, so let's go in and come out fast!
• Friend B: Really? Then you can lead the way. Good luck~
• Seokjun: ....

In fact, Seokjun is more afraid of ghosts than anyone, but he already bragged and there is no way to take it back.

The ghost house is a grid with $N$ rows and $M$ columns, and it is built as follows.

• Empty cell (.): a cell where Seokjun can move.
• Wall (#): a cell where Seokjun cannot move.
• Ghost (0, 1, 2, 3): each digit is the initial direction the ghost faces. (0: right, 1: down, 2: left, 3: up)

If a wall or another ghost is in the direction a ghost faces, its view is blocked, and it cannot see the cells behind that. However, if the ghost's view is not blocked and Seokjun is in the direction it faces, the ghost can spot him no matter the distance. Each ghost turns 90° clockwise every second, and while it is turning, it cannot see Seokjun.

Every second, Seokjun can move to an adjacent empty cell up, down, left, or right, or he can stay where he is.

Seokjun worked at an amusement park before, so he knows the positions of all the ghosts and the map. He wants to escape as quickly as possible without being spotted by any ghost. Please find the way for him.

The first line contains the size of the ghost house $N$ and $M$ ($2 \le N, M \le 200$).

The second line contains the entrance coordinates $S_x, S_y$ and the exit coordinates $E_x, E_y$ ($1 \le S_x, E_x \le N$, $1 \le S_y, E_y \le M$).

Coordinates $(x, y)$ mean the $x$-th cell from the top and the $y$-th cell from the left.

The entrance and the exit are empty cells, and the two coordinates are different. It is guaranteed that no ghost is facing the entrance at time $0$.

The next $N$ lines describe the state of the ghost house.

Print the minimum time needed to escape the ghost house.

If there is no way to escape without being spotted by a ghost, print GG.