Dalam soal interaktif ini, Anda harus pergi dari pintu masuk sebuah labirin yang tidak diketahui menuju pintu keluarnya tanpa menghabiskan terlalu banyak waktu.

Prajurit terkenal Malcolm, sang Pahlawan Arcania, berjalan pada malam hari melalui hutan yang gelap. Ia sudah berjalan lama dan mulai mengira dirinya tersesat, tetapi tiba-tiba menemukan tembok batu di jalannya. Tanda pada lempeng batu yang terlihat di bawah daun-daun berguguran dengan jelas menunjukkan bahwa ia menemukan labirin buatan para kurcaci.

Sang pahlawan hanya tahu sedikit tentang hutan dan pepohonan yang tumbuh di sana. Untungnya, ia menghabiskan banyak waktu bersama para kurcaci, sehingga kini ia dapat mengetahui banyak hal tentang labirin hanya dengan melihat tandanya.

Tanda pada labirin ini membentuk karakter “SK3”. Karakter “S” berarti bahwa labirin berbentuk persegi, yaitu lantainya terdiri atas $n \times n$ petak persegi berukuran $1 \times 1$ meter masing-masing. Ada tembok tipis yang menyambung mengelilingi petak-petak ini dengan dua bukaan. Yang pertama adalah pintu masuk, di dekat tempat sang pahlawan berdiri. Letaknya di dinding selatan petak sudut barat daya labirin. Bukaan kedua adalah pintu keluar yang terletak di dinding utara petak sudut timur laut.

Setiap dua petak yang berbagi sisi dapat dihubungkan oleh jalan atau dipisahkan oleh bagian dinding dalam yang tipis sepanjang satu meter. Dari setiap petak, seseorang dapat berpindah ke petak mana pun yang berbagi sisi dengannya jika tidak ada dinding di antara keduanya. Selain itu, pintu keluar dapat dilewati dengan bebas. Pintu masuk hanya terbuka sampai sang pahlawan melangkah ke dalam labirin. Setelah itu, pintu segera ditutup dan baru dibuka kembali ketika sang pahlawan tiba dengan selamat di pintu keluar.

Karakter “K3” memberi tahu penjelajah labirin berpengalaman bahwa labirin memiliki struktur berikut. Pertama, dari semua bagian dinding dalam tipis yang mungkin (ada $n \times (n-1)$ bagian utara–selatan dan jumlah yang sama untuk timur–barat), dipilih sepertiganya secara acak, dibulatkan ke bawah jika bukan bilangan bulat, lalu dipertimbangkan dalam urutan acak yang tetap. Kemudian bagian-bagian itu dipasang ke labirin menurut urutan tersebut. Jika pemasangan suatu bagian akan membagi persegi yang memuat labirin menjadi bagian-bagian yang tidak terhubung, bagian itu dibuang dan tidak dipasang. Dengan demikian, labirin yang dihasilkan dijamin terhubung.

Malcolm menjadi gembira: ia mengetahui begitu banyak tentang labirin sehingga pasti dapat mencapai pintu keluar. Tujuannya adalah berangkat dari petak hutan yang bersebelahan dengan pintu masuk dan tiba di petak hutan yang bersebelahan dengan pintu keluar. Ia juga harus bergegas: orang yang bergerak dari pintu masuk ke pintu keluar dengan cukup cepat akan melihat harta karun yang tersembunyi di hutan dekat pintu keluar. Tentu saja, hal itu hanya benar jika belum ada orang lain yang mencapai harta karun lebih dahulu.

Namun, setelah dipikirkan lagi, ada hal-hal yang mengkhawatirkan. Pertama, Malcolm tidak mengetahui ukuran labirin: panjang sisi persegi $n$ dapat berupa sembarang bilangan bulat meter dari $10$ sampai $200$. Kedua, labirin sama gelapnya dengan hutan di sekitarnya, sehingga Malcolm harus bergerak hampir tanpa bisa melihat. Pada awal setiap langkah, sang pahlawan memilih satu dari empat arah utama: utara, timur, selatan, atau barat. Kemudian ia mencoba bergerak satu meter ke arah itu. Jika menabrak penghalang, ia tetap di tempat. Jika tidak, ia berpindah ke petak tetangga dalam arah yang dipilih. Waktu setiap langkah tidak bergantung pada hasilnya, sehingga yang penting adalah jumlah seluruh langkah.

Bantu sang pahlawan bergerak agar tiba di petak yang diminta dengan cukup cepat. Solusi dianggap benar jika sang pahlawan melakukan paling banyak $5 \cdot n + 300$ langkah dan tiba di petak di luar pintu keluar labirin.

Interaksi

Dalam soal ini, program juri menanggapi perintah yang dikeluarkan solusi ke keluaran standar. Setiap perintah menentukan langkah Malcolm berikutnya. Setiap perintah ditulis pada baris terpisah dan terdiri atas satu huruf kapital bahasa Inggris: “N” untuk melangkah ke utara, “E” ke timur, “S” ke selatan, dan “W” ke barat.

Untuk setiap perintah, program juri segera menanggapi dengan satu baris yang dikirim ke masukan standar solusi. Baris itu berisi satu kata dengan huruf kecil bahasa Inggris: “no” jika penghalang menghalangi jalan, “ok” jika langkah berhasil tetapi sang pahlawan belum tiba di petak tujuan, dan “end” jika langkah berhasil serta sang pahlawan tiba di petak tujuan. Setelah menerima tanggapan “end”, solusi harus berhenti tanpa mengeluarkan keluaran lagi.

Untuk mencegah keluaran tertahan dalam buffer, kosongkan buffer keluaran setelah setiap perintah. Misalnya, gunakan fflush (stdout) dalam C atau C++, System.out.flush () dalam Java, flush (output) dalam Pascal, atau sys.stdout.flush () dalam Python.

Dalam setiap pengujian, labirin telah ditetapkan sebelumnya setelah dihasilkan secara acak.

Jika solusi telah melakukan setidaknya $100\,000$ langkah, tetapi belum melampaui batas waktu dan belum tiba di petak tujuan, pengujian dihentikan dengan hasil “Jawaban Salah”.

Contoh

Catatan

Gambar di atas menunjukkan labirin yang dihasilkan pada pengujian pertama. Malcolm mulai di petak bertanda lingkaran dan harus tiba di petak bertanda silang. Labirin ini dapat dilalui, misalnya, dengan urutan perintah berikut (di bawah perintah adalah hasil pelaksanaannya):

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

Pada gambar, solusi ini ditunjukkan oleh garis abu-abu tebal.