描述

农夫约翰的奶牛们拒绝参加他组织的马拉松比赛，因为他选择的路线对于它们悠闲的生活方式来说太长了。因此，他希望找到一条长度更合理的路线。这个问题的输入数据与“导航噩梦”（"Navigation Nightmare"）的输入数据相同，随后会有一行包含一个整数 K，表示 K 个“距离查询”。每个距离查询是一行输入，包含两个整数，表示农夫约翰感兴趣的农场编号，他希望计算这两个农场之间的距离（以沿路径上道路的长度之和来衡量）。请尽快回答农夫约翰的距离查询！

输入

第 1 行到第 1+M 行：与“导航噩梦”（"Navigation Nightmare"）问题的输入格式相同。 每行包含四个部分：两个农场的编号、连接这两个农场的道路长度，以及一个方向字符（方向字符可以忽略，因为距离计算只与道路长度有关）。 第 2+M 行：一个单独的整数 K。 $1 ≤ K ≤ 10,000$，表示后续的距离查询数量。 第 3+M 行到第 2+M+K 行：每一行对应一个距离查询，包含两个农场的编号。

输出

第 1 行到第 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

提示

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

来源

USACO 2004 二月赛