자동차 항법

완벽한 자동차를 위한 국제 위원회(ICPC)가 운전자 보조 시스템을 시험하려고 도시 규모의 시험 주행장을 지었다. 당신의 회사인 Automotive Control Machines(ACM)가 이 주행장에서 시험 주행을 맡았다.

주행장은 곧게 뻗은 도로로 이루어져 있고, 각 도로는 동서 방향이거나 남북 방향이다. 막다른 도로는 없어서 도로의 양 끝은 각각 다른 도로와 만난다. 입체 교차로도 없어서 직교하는 두 도로가 같은 지점을 지나면 그 지점에서 만나고, 자동차는 거기서 다른 도로로 방향을 바꿀 수 있다. 유턴은 할 수 없고, 자동차는 도로를 벗어나지 않는다. 도로의 폭은 0이다.

주행장을 달리던 자동차 한 대의 GPS 장치가 고장 나서 운전자가 길을 잃었다. 주행 거리계와 전자 나침반은 아직 작동한다.

GPS가 고장 난 순간, 즉 시각 0에 자동차가 있던 위치는 알고 있다. 그 뒤로는 단위 시간마다 한 번씩 주행 거리계와 나침반을 원격으로 읽는다. 나침반이 가리키는 방향은 북, 동, 남, 서 중 하나다. 자동차가 방향을 바꾸는 바로 그 순간에 나침반을 읽으면, 읽힌 방향은 바꾸기 전 방향일 수도 있고 바꾼 뒤 방향일 수도 있다.

시각 0에 자동차가 향하던 방향은 모른다. 그때 자동차가 달리던 도로와 어긋나지 않는 모든 방향을 고려해야 한다.

지금 자동차가 있을 수 있는 위치를 모두 구하는 프로그램을 작성하시오.

입력은 테스트 케이스 하나로 이루어진다.

첫째 줄에 네 정수 $n$, $x_0$, $y_0$, $t$가 주어진다. $n$은 도로의 수($4 \le n \le 50$), $(x_0, y_0)$은 GPS가 고장 난 시각 0에 자동차가 있던 x좌표와 y좌표, $t$는 현재 시각($1 \le t \le 100$)이다. 점 $(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축은 북쪽을 가리킨다. 입력에 주어지는 좌표는 모두 0 이상 50 이하다.

남은 $t$개 줄에는 각각 정수 $d_i$($1 \le d_i \le 10$)와 문자 $c_i$가 주어진다. $d_i$는 시각 $i - 1$부터 시각 $i$까지 측정된 주행 거리이고, $c_i$는 시각 $i$에 측정된 자동차의 방향으로 북쪽이면 N, 동쪽이면 E, 서쪽이면 W, 남쪽이면 S다.

측정값과 어긋나지 않으면서 시각 $t$에 자동차가 있을 수 있는 위치를 모두 출력한다. 한 줄에 한 위치씩, 두 정수를 공백 하나로 구분해 출력한다.

위치는 사전순으로 정렬한다. 즉 $x_i < x_j$이거나 $x_i = x_j$이면서 $y_i < y_j$이면 $(x_i, y_i)$를 $(x_j, y_j)$보다 먼저 출력한다.

측정값과 어긋나지 않는 위치가 도로 위에 적어도 하나 있다.