Description

约翰有$N$ 个农场，标记为$1$～$N$ 。有$M$ 条垂直和水平的道路连接农场，每条道路的长度各不相同。

每个农场都可以直接连接到北部$（$$N$$）$、南部$（$$S$$）$、东部$（$$E$$）$或西部$（$$W$$）$最多$4$个其他农场。

农场位于道路的终点，正好一条道路连接一对农场，没有两条道路交叉。他希望知道两个农场之间的道路长度，农场的地图如下图所示。

“$1$ $6$ $1$$3$ $E$”表示从$F$$1$到$F$$6$有一条长度为$1$$3$的道路，$F$$6$在$F$$1$的东部。

Format

Input

第$1$行包含两个整数$N$ $（$$2$$≤$$N$ $≤$$4$$0$,$0$$0$$0$$）$和$M$ $（$$1$$≤$$M$$<$$4$$0$,$0$$0$$0$$）$。

第$2$..$M$ +$1$行，每行都包含$4$个字符$a$、$b$、$l$、$d$ ，表示两个农场$a$ 和$b$ 由一条路相连，长度为$l$ $（$$1$$≤$$l$ $≤$$1$$0$$0$$0$$）$，$d$ 是字符“$N$”“$S$”“$E$”或“$W$”，表示从$a$ 到$b$ 的道路方向。

第$M$ +$2$行包含单个整数$K$ $（$$1$$≤$$K$ $≤$$1$$0$,$0$$0$$0$$）$，表示查询个数。

接下来的$K$ 行，每行都包含距离查询的两个农场的编号。

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

来源

POJ1986