题目描述

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

输入格式

第 $1$ 到 $I+M$ 行：与前两题相同。

第 $2+M$ 行：一个整数 $K$（$1≤K≤10000$）。

第 $3+M$ 到 $2+M+K$ 行：每行输入 $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$ 的距离。

题目来源

Green