Новосибирский бизнес-центр "Кобра" славится своими проблемами с температурой. И возникали большие сложности с тем чтобы просто уйти домой. Офис в нем можно представить в виде таблицы размера n x m, каждая клетка которой либо свободна, либо занята стенкой. Изначально, перед уходом все коллеги находятся в некоторой свободной клетке, а выход из офиса находится в другой свободной клетке. Коллеги могут переходить между соседними по стороне свободными клетками.

Температура воздуха меняется мистическим образом. А именно, каждый раз, когда коллеги переходят между двумя клетками, соседними по горизонтали, температура уменьшается на 1 градус, а когда переходят между двумя клетками, соседними по вертикали, температура увеличивается на 1 градус. Температура воздуха может принимать любые целочисленные значения, в том числе, температура может быть отрицательной.

Коллеги хотят, чтобы конечная температура воздуха, когда они выберутся из офиса, как можно меньше отличалась от исходной температуры воздуха. Помогите им определить минимальное возможное отличие исходной температуры от конечной. Обратите внимание, что значения температуры воздуха во время нахождения коллег в офисе, их не интересует. При необходимости, коллеги могут несколько раз проходить через любые свободные клетки, в том числе стартовую клетку и клетку с выходом.

Формат входных данных

В первой строке даны два целых числа n и m - размеры таблицы (1 ⩽ n,m ⩽ 1000). В следующих n строках находится по m символов - описание таблицы. Описание состоит из символов ., #, s и f. Если j-й символ в i-й строке равен #, то в клетке (i, j) находится стенка, иначе эта клетка свободна. Символ s обозначает стартовую позицию коллег, а символ f обозначает клетку, в которой находится выход. Гарантируется, что в таблице содержится ровно один символ s и ровно один символ f.

Формат выходных данных

Если коллеги не смогут выбраться из офиса, выведите -1. Иначе, выведите неотрицательное число - минимальное возможное отличие исходной температуры от конечной, которого они могут добиться.

Пример

Примечание

В первом тесте коллеги могут сначала перейти два раза в клетку сверху, и потом два раза в клетку справа. Тогда, сначала температура увеличится на 2, а после - уменьшится на 2. В итоге, отличие от исходной будет 0 градусов.