Brice Bilson 喜欢在附近的森林（被称为“正交森林”）中慢跑。森林之所以得名，是因为所有的路径（均为双向）都铺设在正交网格上，且所有转弯均为 90 度。Brice 在慢跑时非常挑剔，每当他到达两个或多个路径的交叉点时，总是遵循一套规则。这些规则如下：

1. 如果还有三条分支，Brice 选择中间的那条。
2. 如果只剩下两条分支，Brice 选择他左手边的那条。
3. 如果没有分支可走，Brice 结束慢跑并走向最近的出口。

Brice 在另一方面也很挑剔。他为每条路径分配了一个“兴趣值”，这是一个正整数，表示该路径对他慢跑的吸引力。数值越高，路径越有趣。如果一条路径的兴趣值为 $n$，那么 Brice 在他的慢跑过程中经过该路径的次数不会超过 $n$ 次。在第 $n$ 次经过后，对于 Brice 而言，该路径将不复存在（例如，任何使用该路径的三分支交叉点现在变为两分支交叉点，任何两分支交叉点变为一分支交叉点）。图 L.1 展示了一个例子：

图 L.1：对应样例输入 1 的示例公园

假设 Brice 从左图中的交叉点 D 进入公园并向北行进，图中路径旁边的数字表示他的兴趣水平。他的行程路线为 DFGCBADFGCBA，此时我们到达右图，图中显示了每条路径更新后的兴趣水平，以及从 A 到 B 的路径由于已被遍历 2 次而产生的“移除”。从交叉点 A 开始，Brice 现在遍历路线 ADFGCBEDA，此时他到达死胡同并结束了他的慢跑。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 2500$)，分别表示交叉点的数量和交叉点之间路径的数量。下一行包含 $n$ 对整数，给出交叉点的位置。交叉点按给出的顺序编号为 $1$ 到 $n$，所有位置坐标 $x, y$ 满足 $0 \le x, y \le 10^6$。此后有 $m$ 行，每行包含三个整数 $i, j, k$ ($1 \le i, j \le n, 1 \le k \le 10^6$)，表示在交叉点 $i$ 和 $j$ 之间存在一条兴趣值为 $k$ 的路径。所有路径均为垂直或水平，且除了指定的交叉点外，不会接触任何其他顶点。输入的最后一行包含一个整数 $s$ ($1 \le s \le n$) 和一个字符 $d \in \{N, S, E, W\}$，表示 Brice 从交叉点 $s$ 开始，沿着方向 $d$ 走上第一条路径。从顶点 $s$ 出发，始终会有一条沿着方向 $d$ 的路径。

输出格式

输出 Brice 结束慢跑时的位置。

样例

输入 1

7 8
0 0 5 0 12 0 0 5 5 5 0 10 12 10
1 2 2
2 3 4
4 5 5
6 7 8
1 4 4
2 5 7
3 7 4
4 6 6
4 N

输出 1

0 0