Problem L
A (Fast) Walk in the Woods

Brice Bilson loves to take jogs in a nearby forest known as Orthogonal Woods. The forest gets that name as the paths – all two-way – are laid out along an orthogonal grid, with all turns being 90 degrees. Brice is a bit persnickety when it comes to his jogs, and always follows a set of rules when he reaches an intersection of two or more paths. These rules are

1. If there are three remaining branches, Brice takes the middle one.

2. If there are just two remaining branches, Brice takes the one on his left.

3. If there are no branches to take, Brice ends his jog and walks to the nearest exit.

Brice is persnickety in another way too. He has assigned each path an “interest value”, which is a positive integer indicating how interesting that path is to jog. The higher the value, the more interesting the path is. If the value of a path is $n$, then Brice will jog on that path no more than $n$ times in his jog. After the $n^{\mbox{th}}$ pass that path will cease to exist as far as Brice is concerned (so, for example, any three-branch intersection using that path now becomes a two-branch intersection and any two-branch intersection becomes a one-branch intersection). An example is shown in Figure 1 below:

Figure 1: Sample park corresponding to Sample Input 1

Suppose Brice enters the park at intersection D heading north in the figure on the left, where the numbers next to each path indicate his interest levels. His travels takes him on the route DFGCBADFGCBA at which point we reach the figure on the right, showing the updated interest levels of each path and the “removal” of the path from A to B since it’s now been traversed $2$ times. From intersection A Brice now traverses the route ADFGCBEDA at which point he hits a dead end and ends his jog.

Input

Input starts with two integers $n$ and $m$ ($2 \leq n \leq 2\, 500$) giving the number of intersections and the number of paths between intersections. The next line contains $n$ pairs of integers giving the locations of the intersections. Intersections are numbered from $1$ to $n$ in the order they are presented and all location values $x,y$ satisfy $0 \leq x,y \leq 10^6$. After this are $m$ lines each containing three integers $i$ $j$ $k$ ($1 \leq i,j \leq n, 1 \leq k \leq 10^6$) indicating that a path exists between intersections $i$ and $j$ with interest level $k$. All paths will be either vertical or horizontal and will not touch any other vertices other than the specified intersection points. The final line of input contains an integer $s$ ($1 \leq s \leq n$) and a character $d \in \mbox{\{ N,S,E,W\} }$ indicating that Brice starts his jog by taking the path in direction $d$ from intersection $s$. There will always be a path heading in direction $d$ from vertex $s$.

Output

Output the location where Brice ends his jog.

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