Description

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

Format

Input

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

第2+M行：一个整数K(1≤K≤10000)．

第3+M到2+M+K行：每行输入2个整数，代表两个农场．

Output

对每个问题，输出单独的一个整数，给出正确的距离．

Samples

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

Limitation

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