問題

これは何年前か、誰かがちょんぎった1日のお話。

明日は謎の生物iwashiがつちからはえてきます。iwashiはTSG国にのみ生息する生き物で、天敵はつばめです。その味からTSG国の特産物になってます。
TSG国のfiord君はiwashiの収穫をしたいと思っています。ただ、iwashiは凶暴な生き物で、群れをなして囲まれてしまうととても危険です。今回、TSG国屈指の大企業hakata社が事前にiwashiのはえてくる場所を正確に予測してくれています。安全にfiord君がiwashiの収穫を行えるよう、ナビゲートしてあげてください。

ルール

TSG国はH×Wのマス目で表現されています。北西が(1,1)、南東が(H,W)で表現されます。各マスは「通路」か「壁」のどちらかです。各マスは東西南北の隣接したマスとつながっており、斜めへの移動は出来ません。fiord君やiwashiは通路上を移動し、壁のマスへ行くことは出来ません。
この日はTターンからなります。fiord君は各ターン東西南北のどちらかの方向を選び、1マス進めます（進まなくてもいいです）。進んだ先にiwashiがいるなら収穫を試みます。

iwashiは毎ターン、fiord君か他のiwashiの群れか、近い方へ向けて毎ターンfiord君と同じ速度で移動します。
fiord君が同時に収穫できるiwashiは5匹までです。6匹以上iwashiがいるマスへfiord君が行くと、逆に襲われてケガをしてしまいます。ケガをすると、5ターン治療に費やしてしまうので、気を付けましょう。なお、何故か治療中のfiord君をiwashiは認識できません。
Tターンで収穫するiwashiが最大になるようfiord君の行動を教えてあげて下さい。

iwashiの行動について

具体的には、以下のアルゴリズムで動作します。

1. fiord君(治療中でない)とiwashiがいるマスをソースとして、BFSを行い「最短距離」のマップを生成します。
2. (0,0)→(0,1)→…→(0,W)→(1,0)→…→(1,W)→(2,0)→…→(H,W)の順に、以下のことを行います。
   1. iwashiがいないなら次へ行きます。
   2. 既にそのマスへ外からiwashiがやってくるなら元々そのマスにいたiwashiは動きません。そうでなければ、北→東→南→西の順に、現在位置よりも1のマップ上で距離が短いマスを探し、見つけたらそちらへ移動します。

また、各ターンは、

1. fiord君移動
2. iwashi移動（運悪くiwashiがケガをしているfiord君のマスへ突っ込むときがあります。その際は、治療期間が5ターン増えます）
3. iwashiがつちからはえてくる(fiord君がいるマスへはえてくる可能性もあります)
4. fiord君収穫に挑戦（fiord君がケガをしている間は収穫できません。iwashiが素通りすることもあります） の順になります。

入力

標準入力を用い、以下の形式で与えられます。

H W T N
Px Py
S1
S2
...
SH
x1 y1 t1
x2 y2 t2
...
xN yN tN

TSG国の区画はH×Wです。その区画は{Si | 1≦i≦H}になっています。1≦i≦Hで|Si|=Wが成立し、Sij="#"でそのマスが壁、Sij="."で通路であることを示します。外周は"#"で囲まれていることが保証されています。
現在のfiord君の位置は(Px, Py)です。周囲が壁て囲まれていて動けない可能性があります。
また、この日にfiord君はTターン行動可能です。hakata社のエスパーによると今日はN匹のiwashiがつちからはえてくるらしいです。
i匹目(1≦i≦N)のiwashiは位置(xi, yi)に現在からtiターン後につちからはえてきます。ti=0は既にはえているiwashiです。

出力

S

標準出力で、fiord君の移動方法を1行の文字列Sとして出力してください。 Siが"N"、"E"、"W"、"S"のどれかの時、それぞれの方角に応じた方向へfiord君は動こうとします。 それ以外の文字だった場合や、|S|>Tの時のSi(i>T)、|S|<Tの時の|S|ターン以降の動作は「移動を試みない」という扱いをします。

スコア、テストケース、勝敗の決定方法

テストケースは以下のものを使用します。

• 共通のもの
• H=22
• W=22
• T=1000
• little(6ケース)
• N=250
• 壁と通路の比率: 外周を除いて壁は25%で無作為に生成
• much(6ケース)
• N=3000
• 壁と通路の比率: 外周を除いて壁は25%で無作為に生成
• challenge(3ケース)
• N=1000
• 壁と通路の比率: 外周を除いて壁は47.5%で作為的に生成

スコアは各テストケースで{iwashiの収穫数}/Nで求めます。勝敗は各テストケースのスコアの総和で求めます。
今回の五月祭では全体を通して赤vs青の形式を取っています。この大戦では、ceil(勝者のスコアの総和 - 敗者のスコアの総和)ptが勝利したチームに加算されます。

参考資料

• randomAIのcpp実装
• tester.py
• python tester.py {実行内容}で出来ます。