F. Fantastic Robot
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Fantastic Four have been defeated by the evil Doctor Doom, and are being held hostage in his castle in Latveria, and it's up to HERBIE the robot to save them. HERBIE has managed to infiltrate the castle and now just needs to reach the cell where the Fantastic Four are held to free them.

Doom's castle can be represented as 2D binary matrix of $$$NxM$$$. If a cell has a value of $$$1$$$ it means there is a wall there, while a $$$0$$$ means it's a free space. HERBIE can move only through free spaces, but since he's a robot he can only move in some specific ways.

HERBIE can follow one of 4 possible $$$\bf{instructions}$$$. Assuming HERBIE is on position $$$(x,y)$$$ then:

- $$$U$$$ means HERBIE will try to move to $$$(x-1,y)$$$

- $$$D$$$ means HERBIE will try to move to $$$(x+1,y)$$$

- $$$L$$$ means HERBIE will try to move to $$$(x,y-1)$$$

- $$$R$$$ means HERBIE will try to move to $$$(x,y+1)$$$

If the position HERBIE is trying to move to is a wall or it's outside of the matrix, HERBIE will simply not move and continue with the next instruction.

However HERBIE can't just do any instruction he wants, he has to follow one of its many preprogrammed $$$\bf{orders}$$$. An $$$\bf{order}$$$ is an ordered set of instructions. If HERBIE chooses to execute certain order, then he has to do all of the movements described in it and in their given order, without changing them around.

As time is running out, HERBIE wants to reach the Fantastic Four moving the least amount of time. He has asked you to help him find out the minimum amount of movements he has to do to reach the Fantastic Four and save them! To properly save them HERBIE has to finish at their cell after he completes the instructions of an order. Passing by the cell while not completing an order doesn't count as reaching them.

Input

In the first line two numbers $$$N$$$, and $$$M$$$ ($$$1\leq N,M\leq 10^2$$$), the dimension of the matrix.

In the next $$$N$$$ lines, $$$M$$$ characters $$$1$$$ and $$$0$$$, the matrix representing the map.

In the next line 2 numbers $$$A_x$$$ and $$$A_y$$$($$$0\leq A_x\leq N-1, 0\leq A_y\leq M-1$$$), the place where HERBIE is currently at.

In the next line 2 numbers $$$B_x$$$ and $$$B_y$$$($$$0\leq B_x\leq N-1, 0\leq B_y\leq M-1$$$), the place where the Fantastic Four are being held. Is guaranteed both of these places will have a $$$0$$$ in the matrix.

In the next line a number $$$K$$$($$$1\leq K\leq 10^4$$$) the number of different $$$\bf{orders}$$$ HERBIE knows.

In the next $$$K$$$ lines, a string $$$S_i$$$ made up of $$$U$$$, $$$D$$$, $$$L$$$, $$$R$$$, representing the $$$i$$$-th order HERBIE knows (it is guaranteed the sum of the lengths of all the strings is less than $$$10^4$$$)

Output

A number indicating the minimum number of movements HERBIE will need to do. If it's impossible for HERBIE to reach the Fantastic Four print -1.

Example
Input
2 2
00
10
0 0
1 1
2
RR
D
Output
2