International Commission for Perfect Cars (ICPC) ha construido un circuito de pruebas del tamaño de una ciudad para sistemas avanzados de asistencia al conductor. Tu empresa, Automotive Control Machines (ACM), ha sido designada por ICPC para realizar pruebas de conducción en el circuito.

El circuito consta de calles rectas, cada una orientada de este a oeste o de norte a sur. Ninguna calle tiene un callejón sin salida: en cada extremo se encuentra con otra calle. Tampoco hay calles a distintos niveles, por lo que si dos calles perpendiculares pasan por el mismo lugar, siempre se encuentran en un cruce o una intersección donde el coche puede girar de una a otra. No se permiten giros en U y el coche nunca sale de las calles.

¡Vaya! Acabas de recibir un informe de error: la unidad GPS (Global Positioning System) de un coche que circula por el circuito se ha averiado y el conductor se ha perdido. Afortunadamente, el odómetro y la brújula electrónica siguen funcionando.

Debes escribir un programa que estime la ubicación actual del coche a partir de la información disponible. Conoces su ubicación justo antes de que se averiara el GPS. Además, puedes medir a distancia la distancia recorrida y la dirección del coche una vez por unidad de tiempo. La dirección medida es norte, este, sur u oeste. Si la mides mientras el coche gira, el resultado puede ser la dirección anterior o posterior al giro. Puedes suponer que la anchura de cada calle es cero.

No se conoce la dirección del coche cuando se averió el GPS. Debes considerar todas las direcciones posibles compatibles con la calle por la que circulaba entonces.

Entrada

La entrada consta de un único caso. La primera línea contiene cuatro enteros $n,x_0,y_0,t$: el número de calles ($4\le n\le50$), las coordenadas $x$ e $y$ del coche en el instante cero, cuando se averió el GPS, y el instante actual ($1\le t\le100$), respectivamente. Naturalmente, $(x_0,y_0)$ está en alguna calle. Siguen $n$ líneas; cada una contiene cuatro enteros $x_s,y_s,x_e,y_e$ que describen una calle desde $(x_s,y_s)$ hasta $(x_e,y_e)$, con $(x_s,y_s)\ne(x_e,y_e)$. Como cada calle va de este a oeste o de norte a sur, también se cumple $x_s=x_e$ o $y_s=y_e$. Puedes suponer que dos calles paralelas nunca se solapan ni se encuentran. Los ejes $x$ e $y$ apuntan al este y al norte, respectivamente. Cada coordenada de entrada es no negativa y como máximo $50$. Cada una de las $t$ líneas restantes contiene un entero $d_i$ ($1\le d_i\le10$), la distancia recorrida medida desde el instante $i-1$ hasta $i$, y una letra $c_i$ que indica la dirección medida en el instante $i$: N para norte, E para este, W para oeste o S para sur.

Salida

Escribe todas las ubicaciones actuales posibles del coche compatibles con las mediciones. Si son $(x_1,y_1),(x_2,y_2),\ldots,(x_p,y_p)$ en orden lexicográfico, es decir, $x_i<x_j$ o $x_i=x_j$ e $y_i<y_j$ cuando $1\le i<j\le p$, escribe lo siguiente.

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

Cada línea de salida debe contener dos enteros separados por un espacio.

Puedes suponer que al menos una ubicación en una calle es compatible con las mediciones.

Ejemplos

Entrada 1

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

Salida 1

1 1
2 2

Entrada 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

Salida 2

0 1
1 0
1 2
2 1

Entrada 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

Salida 3

5 5
8 8
10 10
15 5