Коник
Ми знаходимося на ярмарку, де нашу увагу привертає атракціон під назвою "Лабіринт Коника", що складається з рядка батутів, пронумерованих невід'ємними цілими числами:
Відвідувачі стрибають з одного батута на інший, прагнучи дістатися до батута в північно-західному куті, де знаходиться вихід з атракціону. Якщо ви дістанетеся до виходу досить швидко, ви можете виграти приз. Однак, щоб претендувати на приз, необхідно дотримуватися наступного правила: після стрибка з батута, позначеного числом z, ви повинні приземлитися на інший батут, що знаходиться на відстані z батутів у тому ж рядку або стовпці.
Ваше завдання — знайти найкоротший шлях від будь-якого батута до виходу, вимірюваний кількістю стрибків. Оскільки довжина стрибка з кожного батута задана, достатньо позначити кожен батут напрямком оптимального стрибка з нього.
Для заданої початкової позиції шлях вважається коротшим за інший, якщо він вимагає меншої кількості стрибків; у разі рівності перевага надається шляху, перший крок якого веде якомога північніше в рядку; і у разі рівності — якомога західніше.
Замість символів на рисунку ми використовуємо текстові позначення: відповідну сторону світу ('N', 'S', 'E' або 'W') для стрілок, 'X' для батутів без можливого виходу і зірочку '*' для спеціального батута у верхньому лівому куті, який представляє вихід.
Вхідні дані
Кілька випадків дано в одному тестовому файлі. Перша рядок у кожному тестовому випадку містить пару цілих чисел від 1 до 50, розділених пробілом; перше число — це кількість рядків, друге — кількість стовпців у матриці. Потім слідують елементи матриці, рядок за рядком, кожен елемент — невід'ємне ціле число, знову розділене пробілами. Матриця 0×0 позначає кінець тестових випадків і, отже, не повинна аналізуватися.
Вихідні дані
Очікуваний вивід для кожного випадку даних — це матриця символів. Кожен елемент — один з допустимих символів: "N", "S", "E", "W", "X" або "*", як описано вище. Вивід для кожного випадку слідує за порожнім рядком.