У цій інтерактивній задачі потрібно дістатися від входу в невідомий лабіринт до його виходу, витративши не надто багато часу.

Відомий воїн Malcolm, герой Arcania, ішов уночі темним лісом. Він ішов уже довго й почав думати, що заблукав, але раптом натрапив на кам'яну стіну на своєму шляху. Знаки на кам'яній плиті, видимі під опалим листям, чітко вказували, що він знайшов лабіринт, збудований гномами.

Герой мало знає про ліс і дерева, що в ньому ростуть. Натомість він провів багато часу в товаристві гномів, тож тепер може багато дізнатися про лабіринт, лише поглянувши на його позначення.

Позначення на цьому лабіринті утворюють символи «SK3». Символ «S» означає, що лабіринт квадратний, тобто його підлога складається з $n \times n$ квадратних клітинок розміром $1 \times 1$ метр кожна. Навколо цих клітинок проходить тонка суцільна стіна з двома отворами. Перший — це вхід, біля якого стоїть герой. Він розташований у південній стіні південно-західної кутової клітинки лабіринту. Другий отвір — вихід у північній стіні північно-східної кутової клітинки.

Будь-які дві клітинки зі спільною стороною можуть бути з'єднані проходом або розділені метровим відрізком тонкої внутрішньої стіни. З кожної клітинки можна перейти в будь-яку сусідню за стороною клітинку, якщо між ними немає стіни. Крім того, через вихід можна проходити вільно. Вхід відкритий лише до миті, коли герой увійде в лабіринт. Після цього він негайно зачиняється й відчиняється знову лише тоді, коли герой безпечно дістанеться виходу.

Символи «K3» повідомляють досвідченому мандрівникові, що лабіринт має таку структуру. Спочатку з усіх можливих відрізків тонких внутрішніх стін (усього є $n \times (n-1)$ відрізків напрямку північ–південь і стільки ж напрямку схід–захід) випадково вибирають одну третину, округлюючи вниз, якщо число не ціле, і розглядають їх у фіксованому випадковому порядку. Потім відрізки розміщують у лабіринті в цьому порядку. Якщо розміщення якогось відрізка розділило б квадрат, що містить лабіринт, на незв'язні частини, цей відрізок відкидають і не розміщують. Отже, отриманий лабіринт гарантовано зв'язний.

Malcolm зрадів: він знає про лабіринт так багато, що напевно зможе дістатися виходу. Його мета — почати з клітинки лісу, суміжної зі входом, і прийти в клітинку лісу, суміжну з виходом. До того ж слід поспішати: той, хто достатньо швидко пройде від входу до виходу, побачить скарб, схований у лісі поблизу виходу. Звісно, це справедливо лише тоді, коли ніхто не дістався скарбу раніше.

Проте, поміркувавши, можна знайти й привід для занепокоєння. По-перше, Malcolm не знає розміру лабіринту: довжина сторони квадрата $n$ може бути будь-якою цілою кількістю метрів від $10$ до $200$. По-друге, лабіринт такий самий темний, як навколишній ліс, тому Malcolm мусить рухатися майже навпомацки. На початку кожного кроку герой вибирає один із чотирьох основних напрямків: північ, схід, південь або захід. Потім він намагається переміститися на один метр у цьому напрямку. Якщо він наштовхується на перешкоду, залишається на місці. Інакше він переходить до сусідньої клітинки у вибраному напрямку. Час кожного кроку не залежить від його результату, тому важлива загальна кількість кроків.

Допоможіть герою рухатися так, щоб він достатньо швидко дістався потрібної клітинки. Розв'язок вважається правильним, якщо герой зробить не більше $5 \cdot n + 300$ кроків і потрапить у клітинку ззовні виходу з лабіринту.

Взаємодія

У цій задачі програма журі реагує на команди, які розв'язок виводить у стандартний потік виведення. Кожна команда визначає наступний крок Malcolm. Команда записується в окремому рядку й складається з однієї великої англійської літери: «N» — крок на північ, «E» — на схід, «S» — на південь, «W» — на захід.

На кожну команду програма журі негайно відповідає рядком, переданим у стандартне введення розв'язку. Він містить одне слово з малих англійських літер: «no», якщо перешкода завадила пройти; «ok», якщо крок успішний, але герой не досяг цільової клітинки; і «end», якщо крок успішний і герой опинився в цільовій клітинці. Після отримання відповіді «end» розв'язок має завершитися без подальшого виведення.

Щоб уникнути буферизації виведення, очищайте буфер після кожної команди. Для цього можна використати, наприклад, fflush (stdout) у C або C++, System.out.flush () у Java, flush (output) у Pascal або sys.stdout.flush () у Python.

У кожному тесті лабіринт заздалегідь фіксується після випадкової генерації.

Якщо розв'язок зробив принаймні $100\,000$ кроків, але ще не перевищив обмеження часу й не досяг цільової клітинки, тестування припиняється з результатом «Неправильна відповідь».

Приклади

Примітка

На рисунку вище показано лабіринт, згенерований у першому тесті. Malcolm починає в клітинці, позначеній кружечком, і має дістатися клітинки, позначеної хрестиком. Наприклад, цей лабіринт можна пройти за допомогою такої послідовності команд (під командами наведено результати їх виконання):

N W N E N W N E N E E E S E E N N N N N E N E S E E N
ok no ok ok ok ok ok ok ok ok ok no ok ok ok ok ok ok ok ok ok ok ok no ok ok end

На рисунку цей розв'язок показано товстою сірою лінією.