问题描述

约翰的奶牛们拒绝跑他的马拉松，因为她们悠闲的生活不能承受他选择的长长的赛道。因此他决心找一条更合理的赛道。此题的输入于第一题相同，紧接着下一行输入一个整数K,以后K行为K个"距离问题"。每个距离问题包括两个整数，就是约翰感兴趣的两个农场的编号，请你尽快算出这两地之间的距离。

输入格式：

第1行：两个分开的整数N和M。

第2到M+1行：每行包括4个分开的内容，F1,F2,L,D分别描述两个农场的编号，道路的长度，F1到F2的方向N,E,S,W。

第2+M行：一个整数K（1<=K<=10000）.

第3+M..2+M+K:每行表示一个问题，包含两个整数代表两个农场。

输出格式：

第1..K行：对应每个问题，输出单独的一个整数给出正确的距离。

输入样例(dquery.in)：

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

样例(dquery.out)：

13
3
36

输出提示：

农场2 到6 有 20+3+13=36 的距离。

数据范围

2 <= N <= 40,000

1 <= M < 40,000

1 <= length <= 1000