문제
먼저 번에 창호가 고른 마라톤 코스는 너무나도 길어서 소들이 달리기를 거부했다. 그래서 창호는 이번엔 여러 가지 후보 코스들을 정해 놓고, 각 코스의 길이가 얼마나 되는지 알고 싶어 한다.
입력
입력의 첫 줄에 공백으로 구분된 두 개의 정수 N, M이 입력된다.
이후 M개의 줄에 걸쳐 도로의 정보가 입력된다.
각 줄의 첫 번째 숫자와 두 번째 숫자는 도로의 양 끝에 있는 농장의 번호이다. 세 번째 숫자는 도로의 길이를 나타내며, 네 번째 문자는 첫 번째 농장을 기준으로 두 번째 농장의 위치가 어느 방향인지 나타낸다(N은 북쪽, E는 동쪽, W는 서쪽, S는 남쪽).
그 다음 줄에는 창호가 고른 마라톤 코스의 개수 K(1 <= K <= 10,000)가 입력된다.
이후 K개의 줄에 걸쳐 두 개의 농장 번호가 입력된다.
출력
각각의 마라톤 코스에 대해서 해당하는 두 지점 사이의 거리를 출력한다.
예제
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 4
2 6
13
3
36
로그인해야 코드를 작성할 수 있어요.