Problem Description

Given the length and height of a parallelogram, and the coordinates of the entrance and exit, each edge of the parallelogram is colored either black or white. You need to find a path where the edges traversed alternate in color (black to white or white to black) and the path is the shortest possible.

Input Format

The first line contains the length and height of the parallelogram, with values ranging from 1 to 500. The second line provides the coordinates of the entrance and exit. The following character matrix represents the color of each edge of the parallelogram.

Output Format

Output the minimum length of the path.

Sample Input and Output

Sample Input #1

2 1
0 0 2 1
bb
nwwnw
bn

Sample Output #1

6

Sample Input #2

5 4
0 2 5 2
nnbnn
nnnwwbwnnnn
nbbbn
nnwbwwbwwnn
bwwww
nnbwbbwwbnn
nwwwn
nnnnbwbbnnn
nnwnn

Sample Output #2

22

Notes

For the first dataset:

(0, 0) -> (1, 0) -> (0, 1) -> (1, 1) -> (1, 0) -> (2, 0) -> (2, 1)

For the second dataset:

(0, 2) -> (1, 2) -> (1, 1) -> (2, 1) -> (2, 0) ->

(3, 0) -> (3, 1) -> (3, 2) -> (4, 1) -> (3, 1) ->

(3, 0) -> (2, 0) -> (2, 1) -> (1, 1) -> (1, 2) ->

(1, 3) -> (2, 3) -> (2, 4) -> (3, 4) -> (3, 3) ->

(4, 3) -> (4, 2) -> (5, 2)

见题面 Input 部分

见题面 Output 部分