네비게이션 악몽

FJ(Farmer John)가 사는 전원 지역에는 농장이 $N$개($2 \le N \le 40000$) 있으며, 보통 1번부터 $N$번까지 번호가 붙어 있습니다. 길이가 $L$($1 \le L \le 1000$)인 세로 길과 가로 길이 모두 $M$개($1 \le M < 40000$) 있어 농장들을 잇습니다. 지도는 아래 그림처럼 생겼을 수 있습니다. 농장에는 F1부터 F7까지 이름이 붙어 있고, 길의 길이는 괄호 안에 적혀 있습니다. 그림은 축척에 맞지 않습니다.

           F1 --- (13) ---- F6 --- (9) ----- F3
            |                                 |
           (3)                                |
            |                                (7)
           F4 --- (20) -------- F2            |
            |                                 |
           (2)                               F5
            | 
           F7 

각 농장은 정확히 북, 남, 동, 서 방향으로 뻗은 길을 통해 최대 4개의 다른 농장과 직접 연결됩니다. 농장은 길의 끝점에만 있으며, 모든 길의 끝점은 농장입니다. 길끼리는 교차하지 않고, 두 농장을 잇는 경로는 정확히 하나입니다.

FJ는 종이 지도를 잃어버려서 컴퓨터에 있는 백업 자료로 지도를 복원하려고 합니다. 자료에는 길마다 한 줄씩 다음과 같은 정보가 있습니다.

• 농장 #23에서 농장 #17까지 북쪽으로 달리는 길이 10인 길이 있다
• 농장 #1에서 농장 #17까지 동쪽으로 달리는 길이 7인 길이 있다
• ...

FJ가 자료를 찾아보는 동안, 길을 잘 찾지 못하는 이웃 Bob이 다음과 같은 질문을 자주 합니다. 농장 #1과 농장 #23 사이의 맨해튼 거리는 얼마인가요?

FJ는 답할 수 있을 때 Bob에게 답합니다. 위 예시에서 답은 17입니다. 두 점 $(x_1,y_1)$과 $(x_2,y_2)$ 사이의 맨해튼 거리는 $|x_1-x_2| + |y_1-y_2|$이며, 바둑판 모양 도로에서 택시가 두 점을 잇기 위해 이동해야 하는 거리입니다.

FJ가 아직 두 농장 사이의 거리를 알아낼 정보가 부족하면, FJ는 사과하며 -1이라고 답합니다.

첫 줄에는 공백으로 구분된 정수 $N$과 $M$이 있습니다.

2번째 줄부터 $M+1$번째 줄까지는 길 하나를 나타내는 네 값 $F_1$, $F_2$, $L$, $D$가 공백으로 구분되어 있습니다. $F_1$과 $F_2$는 길로 연결된 두 농장의 번호이고, $L$은 길의 길이입니다. $D$는 $F_1$에서 $F_2$로 가는 방향을 나타내는 문자 N, E, S, W 중 하나입니다.

$M+2$번째 줄에는 Bob의 질문 개수를 나타내는 정수 $K$($1 \le K \le 10000$)가 하나 있습니다.

$M+3$번째 줄부터 $M+K+2$번째 줄까지 각 줄에는 Bob의 질문이 공백으로 구분된 정수 $F_1$, $F_2$, $I$로 적혀 있습니다. $F_1$과 $F_2$는 질문에 나오는 두 농장의 번호이고, $I$($1 \le I \le M$)는 Bob이 질문한 시점 직후의 자료 번호입니다. 자료 번호 1은 입력의 2번째 줄에 있습니다.

Bob의 질문 $K$개 각각에 대해, 자료 번호 $I$까지 알 수 있는 두 농장 사이의 맨해튼 거리를 한 줄에 하나씩 출력합니다. 아직 거리를 확정할 수 없다면 -1을 출력합니다.

시각 1에 FJ는 1번과 6번 사이의 거리가 13이라는 것을 압니다. 시각 3에도 1번과 4번 사이의 거리는 여전히 알 수 없습니다. 마지막에 6번 위치는 2번에서 서쪽으로 3, 북쪽으로 7만큼 떨어져 있으므로 거리는 10입니다.