国际完美汽车委员会（ICPC）为高级驾驶辅助系统建造了一个城市规模的测试场地。您的公司，即汽车控制机器（ACM），被ICPC指定在场地上进行测试运行。

测试场地由多条街道组成，每条街道要么东西走向，要么南北走向。测试场地的街道没有死胡同，也就是说，在每条街道的尽头，它都会与另一条街道相连。街道之间也没有立体交叉，因此，如果一对正交的街道穿过同一个地理位置，它们总会在十字路口或丁字路口相遇，汽车可以在那里从一条街道转到另一条街道。测试场地上不允许掉头，汽车也不会驶出街道范围。

糟糕！您刚刚收到一份错误报告，称一辆在测试场地上行驶的汽车的GPS（全球定位系统）单元损坏了，司机迷路了。幸运的是，汽车的里程表和电子罗盘仍然可以使用。

请您编写一个程序，根据现有信息估算汽车当前的位置。您拥有GPS单元损坏前一刻汽车的位置。此外，您可以每隔一个时间单位远程测量一次汽车的行驶距离和方向。汽车的测量方向为北、东、南、西之一。如果您在汽车转弯时测量其方向，测量结果可能是转弯前或转弯后的方向。您可以假设每条街道的宽度为零。

GPS单元损坏时汽车的方向未知。您应该考虑所有与当时汽车所在街道相符的可能方向。

输入格式

输入包含单个测试用例。第一行包含四个整数 $n, x_0, y_0, t$，分别表示街道数量（$4 \le n \le 50$）、GPS单元损坏时（时间为零）汽车的 $x$ 和 $y$ 坐标，以及当前时间（$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) \neq (x_e, y_e)$。由于每条街道要么东西走向，要么南北走向，因此满足 $x_s = x_e$ 或 $y_s = y_e$。您可以假设没有两条平行街道重叠或相交。在此坐标系中，$x$ 轴和 $y$ 轴分别指向东和北。每个输入坐标均为非负且不超过 50。接下来的 $t$ 行，每行包含一个整数 $d_i$（$1 \le d_i \le 10$），指定从时间 $i-1$ 到 $i$ 的测量行驶距离，以及一个字母 $c_i$，表示在时间 $i$ 测量的汽车方向，为 N（北）、E（东）、W（西）或 S（南）中的一个。

输出格式

输出所有与测量结果一致的汽车当前可能位置。如果这些位置按字典序排列为 $(x_1, y_1), (x_2, y_2), \dots, (x_p, y_p)$（即对于 $1 \le i < j \le p$，满足 $x_i < x_j$ 或 $x_i = x_j$ 且 $y_i < y_j$），请按以下格式输出：

$x_1 \ y_1$ $x_2 \ y_2$ $\vdots$ $x_p \ y_p$

每一行输出应包含两个由空格分隔的整数。

您可以假设至少有一个街道上的位置与测量结果一致。

样例

样例输入 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