题目描述

在大海中，有 $n$ 座不确定坐标的岛屿。接下来，会陆续发现这些岛屿之间的相对位置关系，在发现的过程中，系统也会询问一些岛屿之间的距离：

• 若有两岛屿的相对位置关系被发现了，则输入格式为 D a b e，表示岛屿 $a$ 在岛屿 $b$ 的 D 方向 $e$ 公里。D 必须是 ESWN 中的一个字母，分别表示东南西北四个方向，输入数据保证不会有矛盾的情况发生，但有些信息可能是重复多余的。
• 如果输入格式为 ? a b，表示需要查询岛屿 $a$ 在岛屿 $b$ 之间的距离。如果 $a$ 与 $b$ 之间的相对关系尚不确定，则输出 ?。

注意，在计算距离时，所使用的定义是横纵坐标的差的绝对值之和，这种距离定义被称为城市距离或曼哈顿距离，而非常用的欧几里得距离。

输入格式

• 第一行：两个整数 $n$ 与 $m$；
• 接下来 $m$ 行：每行首先有一个字母代表操作的类型，接下来有两个整数表示操作涉及的两座岛屿编号 $a$ 与 $b$：
  • 如果字母是 ‘?’，表示一条查询，输出 $a$ 与 $b$ 之间的距离，若它们之间的距离尚不能确定，则输出 ?；
  • 如果字母是 ‘ESWN’ 中的一个，表示这是一条提供岛屿之间相对位置的消息，这一行除 $a$ 与 $b$ 外，最后还有一个正整数 $e$，表示在 $a$ 的指定方向上与 $b$ 相隔 $e$ 个单位。

输出格式

若干行：对于每个询问，如果相对位置已经确认了，输出它们之间的城市坐标的距离，否则输出一个 ‘?’。

5 7
E 1 5 9
? 1 5
S 5 4 3
? 2 3
N 2 1 6
N 1 3 4
? 2 5

9
?
15

数据范围

$1 \leq n \leq 40,000$ $1 \leq m \leq 100,000$ $1 \leq a,b \leq n$ $1 \leq e \leq 10^9$ $D∈{'N','S','W','E'}$