#3364. [Usaco2004 Feb]Distance Queries 距离咨询

内存限制:128 MiB 时间限制:10 Sec

题目描述

    奶牛们拒绝跑马拉松,因为她们悠闲的生活无法承受约翰选择的如此长的赛道.因此约翰决心找一条更合理的赛道,他打算咨询你.此题的地图形式与前两题相同.但读入地图之后,会有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的距离

数据范围与提示