题目描述

Brice Bilson 喜欢在附近一片名为“正交森林”的林地中慢跑。这片森林之所以得名，是因为其中所有可双向通行的小路都沿正交网格铺设，任何转弯都是 $90$ 度。

Brice 对慢跑路线颇为挑剔。每当到达两条或更多小路相交的路口时，他总会遵循以下规则：

1. 如果还有三个分支可走，他选择中间的分支；
2. 如果只剩两个分支可走，他选择左侧的分支；
3. 如果没有任何分支可走，他就结束慢跑，并步行前往最近的出口。

Brice 在另一个方面也很讲究。他为每条小路指定了一个正整数“兴趣值”，表示沿这条小路慢跑有多有趣；数值越大，小路越有趣。如果一条小路的兴趣值为 $n$，那么在一次慢跑中，Brice 最多会经过这条小路 $n$ 次。第 $n$ 次经过之后，在 Brice 看来，这条小路便不复存在。例如，原先使用这条小路的三分支路口会变成二分支路口，二分支路口则会变成单分支路口。

图 1 给出了一个例子。假设在左图中，Brice 从路口 D 进入公园并朝北前进，每条小路旁的数字表示其兴趣值。他首先沿路线 DFGCBADFGCBA 前进。此时得到右图所示的状态：各条小路的兴趣值已经更新，而 A 与 B 之间的小路因为已经被经过 $2$ 次而被“移除”。接着，他从路口 A 沿路线 ADFGCBEDA 前进，最终遇到死路并结束慢跑。

:::align{center} :::

输入格式

第一行包含两个整数 $n,m$，分别表示路口数量和连接路口的小路数量，其中 $2\le n\le 2500$。

第二行包含 $n$ 对整数，依次给出所有路口的坐标。路口按照输入顺序编号为 $1$ 到 $n$，所有坐标值 $x,y$ 均满足 $0\le x,y\le 10^6$。

接下来 $m$ 行，每行包含三个整数 $i,j,k$，表示路口 $i$ 与路口 $j$ 之间有一条兴趣值为 $k$ 的小路，其中 $1\le i,j\le n$，$1\le k\le 10^6$。所有小路均为竖直或水平线段，并且除指定的端点路口外，不会接触任何其他路口。

最后一行包含一个整数 $s$ 和一个字符 $d\in\{\texttt{N},\texttt{S},\texttt{E},\texttt{W}\}$，表示 Brice 从路口 $s$ 出发，先沿方向 $d$ 的小路开始慢跑，其中 $1\le s\le n$。保证从路口 $s$ 出发一定存在一条朝向 $d$ 的小路。

输出格式

输出 Brice 结束慢跑时所在位置的坐标。

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

0 0