Рабочее место участника

"- А какого роста ты хочешь быть? – спросила наконец Гусеница.

- Ах, все равно, – быстро сказала Алиса. – Только, знаете, так неприятно всё время меняться…"

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

Напишите программу, которая по карте Страны Чудес определяет, как Алиса сможет прийти на крокет к Королеве, изменив свой рост наименьшее количество раз. Если существует несколько путей с одинаковым количеством изменений роста, то программа должна минимизировать количество кусочков гриба, использованных для изменения роста.

В первой строке ввода содержатся два целых числа `N`, `M` (`1\ ≤\ N,\ M\ ≤\ 100`) – размеры Страны Чудес. Далее следует `N` строк, содержащих по `M` символов – карта Страны Чудес. Символ 'A' означает начальное положение Алисы, символ 'Q' – место встречи с Королевой. Символы от '1' до '9' означают двери, цифра указывает, каким должен быть рост Алисы при проходе через эту дверь. Символ '#' означает препятствие, а символ '.' – свободное место. Рост Алисы в начале путешествия равен 1. В конце путешествия рост может быть любым. Для изменения роста на `K` (неважно, уменьшения или увеличения), необходимо потратить `K` кусочков гриба. Гарантируется, что на карте ровно один символ 'A' и один символ 'Q', что никакие двери не располагаются рядом в соседних клетках и что существует путь от 'A' до 'Q' через свободные клетки и клетки с дверями.

Выведите в первой строке два целых числа – минимальное количество изменений роста и минимальное количество использованных кусочков гриба при таком количестве изменений роста. Во второй строке вывести последовательность из символов 'N', 'S', 'W', 'E', которая описывает последовательность перемещений Алисы ('N' – вверх, 'S' – вниз, 'W' – влево, 'E' – вправо). Если существует несколько вариантов такого пути, то вывести любой из них. Путь не должен проходить по одной клетке более одного раза.

3 5
A.3..
9##4#
....Q

1 8
SSEEEE