International Commission for Perfect Cars(ICPC)는 첨단 운전자 보조 시스템을 위한 도시 규모의 시험 코스를 건설했다. 여러분의 회사 Automotive Control Machines(ACM)는 ICPC의 지정을 받아 이 코스에서 시험 주행을 수행한다.

시험 코스는 각각 동서 또는 남북으로 곧게 뻗은 도로로 이루어진다. 막다른 길은 없으며, 각 도로의 양 끝은 다른 도로와 만난다. 입체 교차 도로도 없으므로 서로 수직인 두 도로가 같은 지리적 위치를 지나면 반드시 교차로나 접합부에서 만나고, 자동차는 한 도로에서 다른 도로로 방향을 바꿀 수 있다. 시험 코스에서는 유턴이 허용되지 않으며 자동차는 도로 밖으로 나가지 않는다.

이런! 시험 코스를 달리는 자동차의 GPS(Global Positioning System) 장치가 고장 나 운전자가 길을 잃었다는 오류 보고를 막 받았다. 다행히 자동차의 주행 거리계와 전자 나침반은 여전히 작동한다.

사용할 수 있는 정보로 자동차의 현재 위치를 추정하는 프로그램을 작성해야 한다. GPS 장치가 고장 나기 직전의 자동차 위치를 알고 있다. 또한 매 시간 단위마다 한 번씩 자동차의 주행 거리와 방향을 원격으로 측정할 수 있다. 측정되는 방향은 북쪽, 동쪽, 남쪽, 서쪽 중 하나이다. 자동차가 회전하는 중에 방향을 측정하면 회전 전 또는 회전 후 방향 중 하나가 측정될 수 있다. 각 도로의 폭은 0이라고 가정해도 된다.

GPS 장치가 고장 났을 때 자동차의 방향은 알 수 없다. 당시 자동차가 달리던 도로와 일치하는 모든 가능한 방향을 고려해야 한다.

입력

입력은 하나의 테스트 케이스로 이루어진다. 첫 번째 줄에는 네 정수 $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)$까지의 도로를 나타내는 네 정수 $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$도 만족한다. 평행한 두 도로가 겹치거나 만나지 않는다고 가정해도 된다. 이 좌표계에서 $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}$$

각 출력 줄에는 공백으로 구분한 두 정수가 있어야 한다.

측정값과 일치하는 도로 위 위치가 적어도 하나 있다고 가정해도 된다.

예제

입력 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