Automotive Navigation

The International Commission for Perfect Cars (ICPC) built a city sized test course for driver assistance systems. Your company, Automotive Control Machines (ACM), runs the test drives on that course.

The course is made of straight streets, and each street runs either east to west or north to south. No street has a dead end, so each end of a street meets another street. There are no grade separated crossings either, so whenever two perpendicular streets pass through the same point they meet there, and a car can turn from one street to the other at that point. A car may not make a U-turn, and a car never leaves the streets. Every street has zero width.

The GPS unit of one car broke down while the car was running on the course, and the driver got lost. The odometer and the electronic compass still work.

You know where the car was at the moment the GPS unit broke, which is time 0. From then on you read the odometer and the compass remotely, once every time unit. A compass reading is one of north, east, south, and west. If you read the compass at the exact moment the car is turning, the reading can be the direction before the turn or the direction after it.

The direction the car was heading at time 0 is unknown. Consider every direction that agrees with the street the car was running on at that moment.

Write a program that reports every location where the car can be right now.

The input is a single test case.

The first line contains four integers $n$, $x_0$, $y_0$ and $t$: the number of streets ($4 \le n \le 50$), the x and y coordinates of the car at time 0 when the GPS unit broke, and the current time ($1 \le t \le 100$). The point $(x_0, y_0)$ lies on some street.

Each of the next $n$ lines contains four integers $x_s$, $y_s$, $x_e$, $y_e$ and describes a street running from $(x_s, y_s)$ to $(x_e, y_e)$, where $(x_s, y_s) \ne (x_e, y_e)$. Every street runs east to west or north to south, so $x_s = x_e$ or $y_s = y_e$ holds. No two parallel streets overlap or meet. In this coordinate system the x axis points east and the y axis points north. Every input coordinate is at least 0 and at most 50.

Each of the remaining $t$ lines contains an integer $d_i$ ($1 \le d_i \le 10$), the measured distance the car ran from time $i - 1$ to time $i$, and a letter $c_i$, the measured direction of the car at time $i$, which is N for north, E for east, W for west, or S for south.

Print every location where the car can be at time $t$ that agrees with the measurements. Print one location per line as two integers separated by a single space.

Sort the locations in lexicographic order, so $(x_i, y_i)$ comes before $(x_j, y_j)$ when $x_i < x_j$, or when $x_i = x_j$ and $y_i < y_j$.

At least one location on a street agrees with the measurements.