Dweep

Time Limit: 1 Second    Memory Limit: 32768 KB

In a room with n rows and m columns, Dweep and her child is separated by some laser beams and obstacles. Dweep has to manage to make through the laser beams to rescue her child. She can pour some water on herself and walk through a cell with laser beams, and arrive at a cell without laser beams, when her body is dry again. Dweep can walk in eight directions. Dweep can only pour water in a cell without laser beams, so she is not able to walk over two continuous cells with laser beams. Laser beam stops at obstacle or other laser generator.

It's your turn to tell the minimum number of times Dweep has to pour water onto herself in order to reach the cell of her child.

Input

There are multiple cases in the input, separated with blank lines. Please process to the end of file.

The first line of each case contains integers n and m (1 <= n, m <= 20).

The second line is the place of Dweep and her child, in the form (row, col).

The third line is an integer k, the sum of laser generators and obstacles.

k lines followed, in the form (row, col, type). there are five possible values for type:

u - laser generator facing north
d - laser generator facing south
l - laser generator facing west
r - laser generator facing east
B - obstacle

Output

One number for each case, the minimum number of times Dweep gets wet. If there is no solution, print -1.

Sample Input

3 3
1 1 3 3
2
2 1 r
2 3 B

3 2
1 2 3 1
2
2 1 B
2 2 B

Sample Output

1
-1

Submit

Source: ZOJ Monthly, January 2003