#2487. 距离查询

距离查询

说明

约翰有NN 个农场,标记为1N1~N 。有MM 条垂直和水平的道路连接农场,每条道路的长度各不相同。每个农场都可以直接连接到北部N(N)、南部S(S)、东部E(E)或西部W(W)最多44个其他农场。农场位于道路的终点,正好一条道路连接一对农场,没有两条道路交叉。他希望知道两个农场之间的道路长度,农场的地图如下图所示。1613E“1 6 13 E”表示从F1F1F6F6有一条长度为1313的道路,F6F6F1F1的东部。 image

输入

第1行包含两个整数N2N40,000N (2≤N ≤40,000)M1M<40,000M (1≤M<40,000)。第2..M+12..M +1行,每行都包含4个字符ablda、b、l、d ,表示两个农场aabb 由一条路相连,长度为l1l1000l (1≤l ≤1000)dd 是字符N”“S”“E“N”“S”“E”W“W”,表示从aabb 的道路方向。第M+2M +2行包含单个整数K1K10,000K (1≤K ≤10,000),表示查询个数。接下来的KK 行,每行都包含距离查询的两个农场的编号。

输出

对每个查询,都单行输出两个农场的距离。

样例

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

来源

POJ1986