说明

约翰有$N$ 个农场，标记为$1～N$。有$M$ 条垂直和水平的道路连接农场，每条道路的长度各不相同。每个农场都可以直接连接到北部$（N）$、南部$（S）$、东部$（E）$或西部$（W）$最多$4$个其他农场。农场位于道路的终点，正好一条道路连接一对农场，没有两条道路交叉。他希望知道两个农场之间的道路长度，农场的地图如下图所示。$“1 6 13 E”$表示从$F1$到$F6$有一条长度为$13$的道路，$F6$在$F1$的东部。

输入

第1行包含两个整数$N （2≤N ≤40,000）$和$M （1≤M<40,000）$。第$2..M +1$行，每行都包含4个字符$a、b、l、d$ ，表示两个农场$a$ 和$b$ 由一条路相连，长度为$l （1≤l ≤1000）$，$d$ 是字符$“N”“S”“E”$或$“W”$，表示从$a$ 到$b$ 的道路方向。第$M +2$行包含单个整数$K （1≤K ≤10,000）$，表示查询个数。接下来的$K$ 行，每行都包含距离查询的两个农场的编号。

输出

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

样例

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