题目描述

奶牛们拒绝跑马拉松，因为她们悠闲的生活无法承受约翰选择的如此长的赛道．

因此约翰决心找一条更合理的赛道，他打算咨询你．此题的地图形式与前两题相同．但读入地图之后，会有$\red{K}$个问题．

每个问题包括$\red{2}$个整数，就是约翰感兴趣的$\red{2}$个农场的编号，请眷算出这$\red{2}$个农场间的距离．

输入格式

第$\red{1}$到$\red{I+M}$行：与前两题相同；

第$\red{2+M}$行：一个整数$\red{K(1≤}$$\red{K≤}$$\red{10000)}$．

第$\red{3+M}$到$\red{2+M+K}$行：每行输入$\red{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

提示

农场$\red{2}$到农场$\red{6}$有$\red{20+3+13=36}$的距离