Brice Bilson 喜欢在附近的森林（被称为“正交森林”）中慢跑。森林之所以得名，是因为所有的路径（均为双向）都铺设在正交网格上，且所有转弯均为 90 度。Brice 在慢跑时非常挑剔，每当他到达两个或多个路径的交叉点时，总是遵循一套规则。这些规则如下：
- 如果还有三条分支，Brice 选择中间的那条。
- 如果只剩下两条分支，Brice 选择他左手边的那条。
- 如果没有分支可走，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