Европейская юниорская олимпиада по информатике 2542 года проводится в Стреляндии.Стреляндия имеет форму таблицы из m строк (занумерованных числами от 0 до m - 1) и n столбцов (занумерованных числами от 0 до n - 1), в каждой клетке которой находится город. Пусть (r, c) обозначает клетку, находящуюся в строке r и столбце c. Общежитие,в котором живут участники, находится в клетке (0, 0), а зал соревнований находится в клетке (m - 1, n - 1).

Особенность Стреляндии в том,что в некоторых городах находятся огромные стрелки. За одну операцию стрелку можно повернуть на 90 градусов по часовой стрелке. Изначально каждая стрелка указывает на север, восток, юг или запад. Организаторы олимпиады хотят воспользоваться особенностью своей страны для навигации участников.

Участники олимпиады будут следовать по стрелкам. Из каждого города они будут переходить в соседний город по направлению стрелки. Если они окажутся в городе, в котором нет стрелки, или если они выйдут за границы Стреляндии, они заблудятся и не смогут участвовать в олимпиаде. Организаторы соревнований хотят, чтобы все участники благополучно добрались до зала соревнований из общежития (клетка (0, 0)) в зал соревнований (клетка (m - 1, n - 1)). Для этого они могут повернуть какие-то стрелки. Помогите им определить минимальное число описанных выше поворотов, необходимое для достижения цели, или сообщите, что участники не смогут добраться до зала соревнований при любой ориентации стрелок.

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

Первая строка содержит два целых числа m и n (1 ≤ ​ n, m ​ ≤ 500) - число строк и столбцов. Следующие m строк содержат по n символов,задающих изначальное направление стрелок (N - север, E - восток , S - юг, W - запад, X - нет стрелки). Последний символ последней строки (то есть символ, соответствующий залу соревнований) всегда будет X. Символ N означает направление "вверх", E означает "вправо", S означает "вниз", и W означает "влево". Каждая клетка содержит один из символов: N, E, S, W, X.

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

Выведите минимальное число поворотов стрелок, которые нужно сделать организаторам. Если решения не существует, то выведите -1.

Объяснения к первому примеру

Оптимальное решение - изменить W в клетке (1, 2) на S, повернув стрелку три раза.

Объяснения ко второму примеру

Здесь ничего делать не нужно, участники и так доберутся до зала соревнований.

Объяснения к третьему примеру

Повернуть стрелку в клетке (0, 0) один раз (чтобы получить S), стрелку в клетке (1, 0) два раза (чтобы получить E), и стрелку в клетке (2, 1) один раз (чтобы получить E).