距离咨询

【题目描述】

农夫约翰有$N$（$2<=N<=40000$）个农场，标号$1$到$N$。$M（2<=M<=40000）$条的不同的垂直或水平的道路连结着农场，道路的长度不超过$1000$.这些农场的分布就像下面的地图一样，图中农场用$F_1..F_7$表示：

每个农场最多能在东西南北四个方向连结$4$个不同的农场。此外，农场只处在道路的两端。道路不会交叉而且每对农场间有且仅有一条路径。邻居鲍伯要约翰来导航，但约翰丢了农场的地图，他只得从电脑的备份中修复率。每一条道路的信息如下：

    从农场$23$往南经距离$10$到达农场$17$

    从农场$1$往东经距离7到达农场$17$

    . . .

最近美国过度肥胖非常普遍。农夫约翰为了让他的奶牛多做运动，举办了奶牛马拉松。马拉松路线要尽量长。

奶牛们拒绝跑马拉松，因为她们悠闲的生活无法承受约翰选择的如此长的赛道。因此约翰决心找一条更合理的赛道。他打算咨询你。读入地图之后会有$K$个问题，每个问题包括$2$个整数，就是约翰感兴趣的$2$个农场的编号，请尽快算出这$2$个农场间的距离。

【输入格式】

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

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

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

第$3+M$到$2+M+K$行：每行输入$2$个整数，代表$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 4
2 6

【样例输出】

13
3
36

【提示】

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

【来源】

$Brian$ $Dean,2004$

$USACO$ $2004$ $February$ $Contest$ $Green$ $Problem$ $3$ $Distance$ $Queries$

$Translate$ $by:庄乐$