ЗАДАЧА G

Кратчайший путь с телепортами

Имя входного файла:teleport.in
Имя выходного файла:teleport.out
Ограничение по времени:1 секунда
Ограничение по памяти:64 Мб

На прямоугольной доске N на M клеточек, часть клеток - телепорты. Верхний левый угол -- клеточка с координатами (1,1). В клеточке с координатами (x1,y1) находится «сказочный герой», который желает как можно быстрее попасть в клеточку с координатами (x2,y2). За одну секунду герой может либо переместиться в соседнюю клетку, т.е. клетку, имеющую общую сторону с той, в которой он находится, либо, если в текущей клетке есть телепорт, мгновенно (т.е. за 0 секунд) телепортироваться в любой другой телепорт.
Напишите программу, которая найдёт кратчайший по времени путь из клеточки с координатами (x1,y1) в клеточку с координатами (x2,y2).

Входные данные

В первой строке входного файла записаны два числа N (1<=N<=1000) - количество клеточек по вертикали, M (1<=M<=1000) - количество клеточек по горизонтали. В следующих N строках, в каждой по M символов записана доска. Буква “T” - обозначает телепорт, “.” - обозначает обычную клетку. В следующей строке записаны числа x1, y1, x2, y2.

Выходные данные

В выходной файл выведите единственное число -- минимальное время, за которое «сказочный герой»
может попасть из клеточки (x1,y1) в клеточку (x2,y2).

Пример


teleport.in teleport.out
5 5
.....
.....
.T...
.....
...T.
1 1 5 5
4