eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Подорож у темряві

Подорож у темряві

Ліміт часу 1 секунда
Ліміт використання пам'яті 32 MiB

Петро П’яточкін увесь вечір блукав цікавим лабіринтом та й не помітив, як настала ніч. Опинившись у темряві, він не бачить нічого, крім плану лабіринту на своєму мобільному та зоряного неба, на якому він одразу знайшов Полярну зірку. План лабіринту має форму прямокутної таблиці символів, у якій крапки "." позначають порожні ділянки-квадрати з довжиною сторони в один крок, а ґратки "#" — стіни. Верхній край плану відповідає напряму на північ, правий — на схід.

Петрику потрібно потрапити до виходу, позначеному на плані хрестиком. Цей єдиний вихід займає окрему ділянку і є отвором, у який Петрик впаде одразу, як ступить на ділянку. На жаль, Петрик не знає, у центрі якої саме ділянки він знаходиться.

Маршрутом назвемо послідовність команд вигляду "крок на північ", "крок на південь", "крок на схід" та "крок на захід". Якщо при виконанні вказівок маршруту наступний крок веде у стіну або за межі лабіринту, такий крок пропускають і йдуть далі за маршрутом.

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

Вхідні дані

Перший рядок вхідного файлу містить натуральні числа H та W (1H, W10).

Кожний з наступних H рядків містить по W символів ".", "#" або "+", які позначають відповідно порожню ділянку, стіну та вихід. Таким чином подано план лабіринту, у якому перший рядок відповідає північному краю лабіринту, а останні символи кожного рядка — східному краю лабіринту.

Вихідні дані

Єдиний рядок вихідного файлу містить послідовність символів, що містить лише символи "N", "S", "E" та "W", які задають напрямок руху відповідно на північ, на південь, на схід і на захід. Цей рядок задає маршрут, дотримуючись якого, Петрик за скінченну кількість кроків прийде до виходу незалежно від свого початкового розташування. Таких маршрутів може бути кілька. Вивести потрібно будь-який із них, у якому кількість кроків не перевищує 10000.

Якщо такого маршруту немає, вихідний файл має містити 2 символи: "NO".

Пояснення: Розглянемо приклад 3. Легко перевірити, що, з якої клітини ми б не почали, рано чи пізно опинимося у виході.

Наприклад, почнемо з ділянки (2, 1) у другому рядку і першому стовпчику.

Наступні кроки в маршруті не мають значення, бо вже дійшли до виходу.