题目描述

农夫约翰有$\red{N(2≤}$$\red{N≤}$$\red{40000)}$个农场，标号$\red{1}$到$\red{N,M(2≤}$$\red{M≤}$$\red{40000)}$条的不同的垂直或水平的道路连结着农场，道路的长度不超过$\red{1000.}$这些农场的分布就像下面的地图一样，

图中农场用$\red{F1..F7}$表示, 每个农场最多能在东西南北四个方向连结$\red{4}$个不同的农场．此外，农场只处在道路的两端．道路不会交叉且每对农场间有且仅有一条路径．

邻居鲍伯要约翰来导航，但约翰丢了农场的地图，他只得从电脑的备份中修复了．每一条道路的信息如下：

从农场$\red{23}$往南经距离$\red{10}$到达农场$\red{17}$

从农场$\red{1}$往东经距离$\red{7}$到达农场$\red{17}$

当约翰重新获得这些数据时，他有时被的鲍伯的问题打断："农场$\red{1}$到农场$\red{23}$的曼哈顿距离是多少？"

所谓在$\red{(X1，}$$\red{Y1)}$和$\red{(X2，}$$\red{y2)}$之间的"曼哈顿距离"，就是$\red{|x| - X21+|y| - y21}$．如果已经有足够的信息，约翰就会回答这样的问题（在上例中答案是$\red{17}$），否则他会诚恳地抱歉并回答$\red{-1.}$

输入格式

第$\red{1}$行：两个分开的整数$\red{N}$和$\red{M.}$

第$\red{2}$到$\red{M+1}$行：

每行包括$\red{4}$个分开的内容，$\red{F1，}$$\red{F2，}$三，$\red{D}$分别描述两个农场的编号，道路的长度，$\red{F1}$到$\red{F2}$的 方向$\red{N，}$$\red{E，}$$\red{S，}$$\red{W}$．

第$\red{M+2}$行：一个整数，$\red{K(1≤}$$\red{K≤}$$\red{10000)，}$表示问题个数．

第$\red{M+3}$到$\red{M+K+2}$行：

每行表示一个问题，由$\red{3}$部分组成：$\red{F1，}$$\red{F2，}$其中$\red{F1}$和$\red{F2}$表示两个被问及的农场．而$\red{(1≤}$$\red{J≤}$$\red{M)}$表示问题提出的时刻．$\red{J}$为$\red{1}$时，表示得知信息$\red{1}$但未得知信息$\red{2}$时．

输出格式

第$\red{1}$到$\red{K}$行：每行一个整数，回答问题．表示两个农场间的曼哈顿距离．不得而知则输出$\red{-1.}$

样例

输入样例

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
1 4 3
2 6 6

输出样例

13
-1
10

提示

在时刻$\red{1，}$约翰知道$\red{1}$到$\red{6}$的距离为$\red{13}$;在时刻$\red{3，}$$\red{1}$到$\red{4}$的距离仍然不知道；在时刻$\red{6，}$位置$\red{6}$向

北$\red{3}$个距离，向西$\red{7}$个距离于位置$\red{2，}$所以距离为$\red{10.}$