描述

在听说美国肥胖流行病后，农夫约翰希望他的牛能多锻炼，所以他承诺为他的牛创建一场牛马拉松。马拉松路线将包括一对农场和一条由它们之间的一系列道路组成的小路。由于农夫约翰希望牛能尽可能多地锻炼，他想要找到地图上相互间距最远的两个农场（距离是通过它们之间道路的总长度来测量的）。帮助他确定这对最远农场之间的距离。

输入

*第1行.....: 与$Navigation Nightmare$相同的输入格式。

(*第1行: 两个用空格分隔的整数: N 和 M。

*第2行至第M+1行: 每行包含四个用空格分隔的元素: F1、F2、L 和 D，用于描述一条道路。F1 和 F2 是这条道路连接的两个农场的编号。L 是这条道路的长度。D 是一个字符，表示道路从 F1 到 F2 的方向，可以是 'N'（北）、'E'（东）、'S'（南）或 'W'（西）。

*第M+2行: 一个单独的整数$K（1 ≤ K ≤ 10,000）$，代表农夫鲍勃提出的查询次数。

*第M+3行至第M+K+2行: 每行对应鲍勃提出的一个查询，包含三个用空格分隔的整数: F1、F2 和 I。 F1 和 F2 是查询中涉及的两个农场的编号。 I 是一个索引$（1 ≤ I ≤ M）$，表示鲍勃是在数据输入到哪一条道路（即第 I 条道路）之后提出这个查询的。 数据索引 1 对应输入数据的第 2 行（即第一条道路的信息）。 数据索引 2 对应第 3 行，以此类推。)

输出

一行：一个整数，表示最远一对农场之间的距离。

样例输入

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

样例输出

52

提示

最长的马拉松从农场2出发，经过道路4、1、6和3到达农场5，全长20+3+13+9+7=52。

来源

USACO 2004 二月赛