International Commission for Perfect Cars（ICPC）は、先進運転支援システムのために都市規模の試験コースを建設した。あなたの会社 Automotive Control Machines（ACM）は、ICPC からそのコースで試験走行を行うように指定された。

試験コースは、それぞれ東西または南北にまっすぐ延びる道路からなる。行き止まりの道路はなく、各道路の端では別の道路と接している。立体交差もないため、直交する 2 本の道路が同じ地理的な位置を通る場合、必ず交差点や分岐点で接し、車は一方から他方へ曲がれる。試験コースでは U ターンは禁止され、車は道路の外へ出ない。

おっと！試験コースを走る車の GPS（Global Positioning System）装置が故障し、運転手が道に迷ったというエラー報告が届いた。幸いにも、車の走行距離計と電子コンパスはまだ動いている。

利用できる情報から車の現在位置を推定するプログラムを作成してほしい。GPS 装置が故障する直前の車の位置は分かっている。また、各単位時間に 1 回、車の走行距離と方向を遠隔測定できる。測定される方向は北、東、南、西のいずれかである。車が曲がっている間に方向を測定した場合、曲がる前または後の方向のいずれかが測定結果になりうる。各道路の幅は 0 と仮定してよい。

GPS 装置が故障したときの車の方向は分からない。そのとき走っていた道路と整合するすべての可能な方向を考慮しなければならない。

入力

入力は 1 つのテストケースからなる。最初の行には 4 つの整数 $n,x_0,y_0,t$ が与えられる。それぞれ道路数（$4\le n\le50$）、GPS 装置が故障した時刻 0 における車の $x$ 座標と $y$ 座標、現在時刻（$1\le t\le100$）を表す。$(x_0,y_0)$ は当然いずれかの道路上にある。続く $n$ 行の各行には、$(x_s,y_s)$ から $(x_e,y_e)$ までの道路を表す 4 つの整数 $x_s,y_s,x_e,y_e$ が与えられ、$(x_s,y_s)\ne(x_e,y_e)$ である。各道路は東西または南北に延びるため、$x_s=x_e$ または $y_s=y_e$ も成り立つ。平行な 2 本の道路は重なったり接したりしないと仮定してよい。この座標系では $x$ 軸と $y$ 軸はそれぞれ東と北を向く。入力される各座標は非負で、最大 $50$ である。残りの $t$ 行の各行には、時刻 $i-1$ から $i$ までの測定走行距離を表す整数 $d_i$（$1\le d_i\le10$）と、時刻 $i$ に測定した方向を表す文字 $c_i$ が与えられる。$c_i$ は北を表す N、東を表す E、西を表す W、南を表す S のいずれかである。

出力

測定結果と整合する車の現在位置をすべて出力せよ。辞書順に $(x_1,y_1),(x_2,y_2),\ldots,(x_p,y_p)$ とする。すなわち、$1\le i<j\le p$ のとき $x_i<x_j$、または $x_i=x_j$ かつ $y_i<y_j$ である。次の形式で出力せよ。

$$\begin{array}{ll}x_1&y_1\\x_2&y_2\\\vdots&\\x_p&y_p\end{array}$$

各出力行は空白で区切られた 2 つの整数からなる。

測定結果と整合する道路上の位置が少なくとも 1 つ存在すると仮定してよい。

入出力例

入力 1

4 2 1 1
1 1 1 2
2 2 2 1
2 2 1 2
1 1 2 1
9 N

出力 1

1 1
2 2

入力 2

6 0 0 2
0 0 2 0
0 1 2 1
0 2 2 2
0 0 0 2
1 0 1 2
2 0 2 2
2 E
7 N

出力 2

0 1
1 0
1 2
2 1

入力 3

7 10 0 1
5 0 10 0
8 5 15 5
5 10 15 10
5 0 5 10
8 5 8 10
10 0 10 10
15 5 15 10
10 N

出力 3

5 5
8 8
10 10
15 5