(빠른) 숲속 산책

브라이스 빌슨은 가까운 숲인 Orthogonal Woods에서 조깅하기를 좋아한다. 이 숲은 모든 길이 양방향이고 직각 격자를 따라 놓여 있으며, 모든 굽이가 90도여서 이런 이름이 붙었다. 브라이스는 조깅에 대해 조금 까다로워서, 두 개 이상의 길이 만나는 교차점에 이를 때마다 정해진 규칙을 따른다. 규칙은 다음과 같다.

1. 남은 갈래가 세 개이면 가운데 길을 택한다.
2. 남은 갈래가 두 개뿐이면 왼쪽 길을 택한다.
3. 택할 갈래가 없으면 조깅을 끝내고 가장 가까운 출구로 걸어간다.

브라이스는 다른 면에서도 까다롭다. 그는 각 길마다 "관심도"라는 양의 정수를 매겨 두었다. 관심도는 그 길을 달리는 재미가 얼마나 큰지를 나타내며, 값이 클수록 재미있는 길이다. 길의 관심도가 $n$이면 브라이스는 조깅 중에 그 길을 최대 $n$번만 지난다. $n$번째 통과 이후에는 그 길이 브라이스에게 없는 것으로 취급된다. 예를 들어 그 길을 포함하던 세 갈래 교차점은 두 갈래 교차점이 되고, 두 갈래 교차점은 한 갈래 교차점이 된다. 그림 L.1에 예가 나와 있다.

그림 L.1: 샘플 입력 1에 해당하는 공원

브라이스가 왼쪽 그림의 교차점 D에서 북쪽을 향해 공원에 들어간다고 하자. 각 길 옆의 숫자는 관심도다. 그는 경로 DFGCBADFGCBA를 따라 이동하고, 이때 A와 B를 잇는 길은 두 번 지나서 제거된다. 오른쪽 그림은 갱신된 관심도와 이 제거된 길을 보여 준다. 교차점 A에서 브라이스는 경로 ADFGCBEDA를 따르며, 막다른 곳에 이르러 조깅을 끝낸다.

첫 줄에는 교차점의 수 $n$과 교차점 사이의 길의 수 $m$이 주어진다($2 \leq n \leq 2\,500$). 다음 줄에는 교차점의 위치를 나타내는 정수 쌍 $n$개가 주어진다. 교차점은 입력된 순서대로 1부터 $n$까지 번호가 매겨지며, 모든 위치 값 $x,y$는 $0 \leq x,y \leq 10^6$을 만족한다. 이어서 $m$개의 줄에 각각 정수 $i$ $j$ $k$($1 \leq i,j \leq n$, $1 \leq k \leq 10^6$)가 주어지며, 이는 교차점 $i$와 $j$를 잇고 관심도가 $k$인 길이 있다는 뜻이다. 모든 길은 가로 또는 세로이며, 지정된 교차점 외의 다른 교차점에는 닿지 않는다. 마지막 줄에는 정수 $s$($1 \leq s \leq n$)와 문자 $d \in \{N,S,E,W\}$가 주어진다. 이는 브라이스가 교차점 $s$에서 방향 $d$의 길을 택하며 조깅을 시작한다는 뜻이다. 교차점 $s$에서 방향 $d$로 향하는 길은 항상 존재한다.

브라이스가 조깅을 끝내는 위치를 출력한다.