농부 존의 목장 이웃은 N개의 농장 (순서대로 1부터 N)을 가지고 있다. M개의 가지각색의 길이를 가진 수직, 수평의 길들은 농장들을 연결한다.

이런 농장들의 맵은 F1..F7 로 명확하게 이름붙여진 농장들과 연결된 사이의 길이는 연결된 농장들은 다음 그림과 같이처럼 보여준다.

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

존은 그의 농장 지도 복사본을 잃어놔렸고, 그는 그의 컴퓨터 안의 백업된 정보로 그것을 재구축하길 원한다. 이 데이터는 다음과 같이 포함되어있다.

#23 농장에서부터 #17까지는 북쪽으로 10걸음 길이의 길이 있다. 
#1 농장에서부터 #17까지는 동쪽으로 7걸음 길이의 길이 있다. 
... 

#1과 #23의 맨하탄 거리는 몇인가?

존은 그가 가능할 때, Bob에게 답해준다. (때때로 그는 아직 데이타가 충분하지 않다.) 위의 예의 정답은 17이고, 밥은 한쌍의 농장들 사이의 맨하탄 거리를 알길 원한다. 두 점 (x1,y1)과 (x2,y2) 사이의 맨하탄 거리는 |x1-x2| + |y1-y2| 이다. (**반드시 길을 따라서 이동하지 않아도 된다.)

밥이 한쌍의 특정 농장에 대해 물어볼 때, 존은 그들 사이의 거리를 추론한 정보가 아직 충분하지 않을 수 있다. 이런 경우, 존은 사과하며 "-1"이라 답한다.

입력

• 첫번째 줄에는 N과 M이 입력된다. (2 <= N <= 40,000) , (1 <= M < 40,000)
• 두번째 줄에서 M줄동안 길을 설명하는 F1, F2, L, D가 공백으로 떨어져서 입력된다. F1 과 F2 는 길로 연결되는 두 농장들이고, L은 길이, 그리고 D는 방향을 뜻하는 'N','E','S','W'로 F1에서 F2까지의 방향이 주어진다. (1 <= L <= 1000)
• 그 다음 줄은 FB의 질문의 개수인 K가 입력된다.
• 이후 K줄 동안 밥으로부터 질문에 해당하는 F1, F2, I가 스페이스로 떨어져서 입력된다. F1과 F2 는 질문의 농장들이고, I( 1<= I <= M)는 질문에 답하는 순간이다. 데이터 인덱스 1은 입력 데이터 2번째 줄 위이다.

출력

입출력 예

입력 

7 6 
1 6 13 E 
6 3 9 E 
3 5 7 S 
4 1 3 N 
2 4 20 W 
4 7 2 S 
3 
1 6 1 
1 4 3 
2 6 6 

출력 

13 
-1 
10 

힌트

1에, FJ는 1과 6사이의 거리가 13인 것을 안다. 

3에, 1과 4사이의 거리를 아직은 모른다. 

마지막에는, 2에서 서쪽으로 7칸, 북쪽으로 3칸을 가면 되므로 거리는 10이다. 

출처: USACO 2004 February
번역: Ceil
추천: ainta