Xét một mê cung tạo bởi các tam giác đều. Mỗi đỉnh được mô tả bởi hai tọa độ \(x,y\) như trong hình. Một số cạnh có một vòng tròn trắng hoặc đen.

Việc di chuyển tuân theo hai quy tắc:

• chỉ được đi qua cạnh có vòng tròn;
• màu các vòng tròn đi qua phải xen kẽ trắng, đen. Ở bước đầu tiên có thể đi qua vòng tròn thuộc một trong hai màu.

Hãy tìm độ dài đường đi ngắn nhất từ lối vào đến lối ra. Độ dài là số cạnh (hay số vòng tròn) đã đi qua. Dữ liệu bảo đảm luôn tồn tại một đường đi như vậy.

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(W,H\) (\(1 \le W,H \le 500\)), là chiều rộng và chiều cao của mê cung.

Dòng thứ hai gồm \(X_1,Y_1,X_2,Y_2\) (\(0 \le X_1,X_2 \le W\), \(0 \le Y_1,Y_2 \le H\)). \((X_1,Y_1)\) là lối vào và \((X_2,Y_2)\) là lối ra.

\(2H+1\) dòng tiếp theo mô tả các cạnh. Các dòng lẻ trong phần này mô tả cạnh nằm ngang và có đúng \(W\) ký tự; các dòng chẵn mô tả cạnh không nằm ngang và có đúng \(2W+1\) ký tự. Không có khoảng trắng giữa các ký tự. Ký tự n nghĩa là cạnh không có vòng tròn, w là vòng tròn trắng và b là vòng tròn đen.

Dữ liệu ra

In một số nguyên duy nhất: độ dài đường đi ngắn nhất từ lối vào đến lối ra.

Ví dụ

2 1
0 0 2 1
bb
nwwnw
bn

6

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

22