题目描述

农民约翰的牧区有N个农场（2 <=N <= 40,000），通常编号/标记为1..N。一系列M （1 <= M < 40000）条不同长度（1 <=长度<= 1000）的垂直和水平道路连接着农场。这些农场的地图可能类似于下图，其中农场被标记为F1。F7的清晰度和连接农场之间的长度如图(n)所示：
        F1 --- (13) ---- F6 --- (9) ----- F3

        |                                 |

       (3)                                |

        |                                (7)

       F4 --- (20) -------- F2            |

        |                                 |

       (2)                               F5

        | 

       F7 
作为一个ascii图，它当然不能精确地缩放。
每个农场可以通过通往北、南、东或西的道路直接连接到最多四个其他农场。此外，农场只位于道路的端点，并且在每条道路的每个端点都可以找到一些农场。没有两条路交叉，只有一条路（道路序列）连接着每一对农场。
农夫约翰（Farmer John）的奶牛拒绝参加他的马拉松比赛，因为他选择的路径对于它们悠闲的生活方式来说太长了。因此，他想找一条长度更合理的路径。  
每个距离查询是一行输入，包含两个整数，表示两个农场的编号，农夫约翰想要计算这两个农场之间的距离（距离以连接两个农场的道路总长度来衡量）。请尽快回答农夫约翰的距离查询！

输入格式

第 1 行：两个空格分隔的整数：N 和 M
第 2 行到第 M+1 行：每行包含四组用空格分隔的数据：F1, F2, L 和 D，用于描述一条道路。F1 和 F2 是该道路连接的两个农场的编号，L 是道路的长度，D 是一个字符（取值为 'N', 'E', 'S' 或 'W'），表示该道路从 F1 指向 F2 的方向。
第 M+2 行：一个整数 K (1 <= K <= 10,000)，表示农夫约翰（Farmer John）的查询数量。
第 M+3 行到第 M+K+2 行：每行对应一个距离查询，包含两个农场的编号。

输出格式

第 1 行到第 K 行：对于每个距离查询，输出一行一个整数，表示相应的距离。

样例

input

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

output

13
3
36

提示

农场 2 和农场 6 之间的距离是 20 + 3 + 13 = 36。