このインタラクティブ問題では、未知の迷路の入口から出口まで、あまり時間をかけずに進まなければなりません。

Arcania の英雄である有名な戦士 Malcolm は、夜、暗い森を歩いていました。長い間歩き、道に迷ったのではないかと思い始めたところ、突然、行く手の石壁に出くわしました。落ち葉の下に見える石板の印は、彼がドワーフの造った迷路を見つけたことをはっきりと示していました。

英雄は森やそこに生えている木についてほとんど知りません。一方、ドワーフたちと長く過ごしたおかげで、今では迷路の印を見るだけで、その迷路について多くのことが分かります。

この迷路の印は「SK3」という文字を形作っています。「S」は迷路が正方形であることを表します。つまり、迷路の床は大きさ $1 \times 1$ メートルの正方形のマスが $n \times n$ 個並んでいます。マスの周りには薄い連続した壁があり、二つの開口部があります。一つ目は英雄のいる場所の近くにある入口で、迷路の南西隅のマスの南側の壁にあります。二つ目は出口で、迷路の北東隅のマスの北側の壁にあります。

辺を共有する二つのマスは、通路でつながっている場合と、長さ一メートルの薄い内壁で隔てられている場合があります。間に壁がなければ、あるマスから辺を共有する隣のマスへ移動できます。また、出口は自由に通り抜けられます。入口は英雄が迷路に入るまでだけ開いています。その直後に閉じ、英雄が無事に出口に到着したときにだけ再び開きます。

「K3」は、経験豊かな迷路探索者に、迷路が次の構造を持つことを伝えます。まず、考えられるすべての薄い内壁の区間（南北方向に $n \times (n-1)$ 区間あり、東西方向にも同じ数あります）から三分の一を無作為に選びます（整数でなければ切り捨てます）。それらを無作為に定めた順序で考え、その順に迷路へ配置します。ある壁を置くと迷路を含む正方形が連結でない部分に分かれる場合、その壁は捨てて配置しません。このため、できあがる迷路は連結であることが保証されます。

Malcolm は喜びました。迷路についてこれだけ知っているのですから、きっと出口にたどり着けます。彼の目標は、入口に隣接する森のマスから出発し、出口に隣接する森のマスに到着することです。さらに、急がなければなりません。入口から出口へ十分速く進んだ者は、出口近くの森に隠された宝を見つけられます。もちろん、誰も先に宝を手に入れていない場合に限ります。

しかし、考え直してみると心配事もあります。第一に、Malcolm は迷路の大きさを知りません。正方形の一辺 $n$ は $10$ から $200$ メートルまでの任意の整数です。第二に、迷路は周りの森と同じように暗いため、Malcolm はほとんど何も見えないまま進まなければなりません。各歩の最初に、英雄は北、東、南、西の四つの方角から一つを選びます。そしてその方向へ一メートル移動しようとします。障害物にぶつかると、その場にとどまります。そうでなければ、選んだ方向の隣のマスへ移動します。一歩にかかる時間は結果に依存しないため、重要なのは総歩数です。

英雄が目標のマスに十分速く到着できるように助けてください。英雄が $5 \cdot n + 300$ 歩以下で迷路の出口の外にあるマスに到着すれば、解答は正しいと判定されます。

インタラクション

この問題では、ジャッジプログラムは解答プログラムが標準出力に出した命令に応答します。各命令は Malcolm の次の一歩を決めます。命令は一行に一つ、大文字の英字一文字で書きます。「N」は北、「E」は東、「S」は南、「W」は西への一歩を表します。

各命令に対し、ジャッジプログラムは直ちに解答プログラムの標準入力へ一行を返します。その行には小文字の英単語一つが含まれます。「no」は障害物に通行を妨げられたこと、「ok」は移動に成功したが目標のマスには到着していないこと、「end」は移動に成功し目標のマスに到着したことを表します。「end」を受け取った後は、それ以上何も出力せずにプログラムを終了しなければなりません。

出力がバッファに残ることを防ぐため、命令を出すたびに出力バッファをフラッシュしてください。例えば、C または C++ では fflush (stdout)、Java では System.out.flush ()、Pascal では flush (output)、Python では sys.stdout.flush () を使用できます。

各テストの迷路は、無作為に生成された後、あらかじめ固定されています。

解答が $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

図では、この解答を太い灰色の線で示しています。