题目描述

农夫约翰有 $n$ 个农场，标号 $1$ 到 $n$，有 $m$条的不同的垂直或水平的道路连结着农场。这些农场的分布就像下面的地图一样：

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

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

• 从农场 $23$ 往南经距离 $10$ 到达农场 $17$
• 从农场 $1$ 往东经距离 $7$ 到达农场 $17$

当约翰重新获得这些数据时，他有时被的鲍伯的问题打断：「农场 $1$ 到农场 $23$ 的曼哈顿距离是多少？」 所谓在 $(x_1，y_1)$ 和 $(x_2, y_2)$ 之间的「曼哈顿距离」，就是 $|x_1 - x_2|+|y_1 - y_2|$。如果已经有足够的信息，约翰就会回答这样的问题（在上例中答案是 $17$），否则他会诚恳地抱歉并回答 $-1$。

输入格式

第 $1$ 行：两个分开的整数 $n$ 和 $m$ 。

第 $2 \sim m+1$ 行：每行包括 $4$ 个分开的内容，$F_1, F_2, S, D$ 分别描述两个农场的编号，道路的长度， $F_1$ 到 $F_2$ 的方向（$N, E, S, W$）。

第 $m+2$ 行：一个整数 $k$ 表示问题个数。

第 $m+3$ 到 $m+k+2$ 行：每行表示一个问题，由 $3$ 部分组成：$F_1, F_2, j$。其中 $F_1$ 和 $F_2$ 表示两个被问及的农场。而 $J$ 表示问题提出的时刻。当 $J$ 为 $1$ 时表示当前得知信息 $1$ 但未得知信息 $2$。

输出格式

第 $1$ 到 $K$ 行：每行一个整数，表示两个农场间的曼哈顿距离，未知则输出 $-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

提示

在时刻 $1$，约翰知道 $1$ 到 $6$ 的距离为 $13$； 在时刻 $3$，$1$ 到 $4$ 的距离仍然不知道； 在时刻 $6$，位置 $6$ 向北 $3$ 个距离，向西 $7$ 个距离于位置 $2$ ，所以距离为 $10$。

数据范围与约定

对于 $100\%$ 的数据，$2 \leq n,m \leq 40000, 1 \leq K \leq 10000, 1 \leq J \leq M$ ，道路的长度不超过一千。