我们想要开发一款智能手机应用程序，帮助购物中心的访客计算商场内两点之间的最短路径。给定访客的当前位置和目的地，应用程序将显示到达目的地的最短步行路径（以米为单位）。

购物中心有 $N$ 个地点，分布在多个楼层，通过步行路径、电梯、楼梯和自动扶梯（自动楼梯）连接。请注意，以米为单位的最短路径可能涉及逆向使用自动扶梯。我们只计算访客实际步行的距离，因此地点之间每种移动方式的成本（以米为单位）各不相同：

• 如果是步行或走楼梯，距离为两点之间的欧几里得距离。
• 使用电梯的成本为 $1$ 米，因为一旦进入电梯，我们就不需要再步行了。一部电梯只能连接 $2$ 个点。实际的电梯连接不同楼层的相同位置，地图中所有由电梯连接的点都有相应的边，因此你无需担心这一点。例如，如果有三层楼，且每个楼层的 $(1,2)$ 位置都有一部电梯，则输入中会包含边 $(0, 1, 2) \to (1, 1, 2)$，$(1, 1, 2) \to (2, 1, 2)$ 以及 $(0, 1, 2) \to (2, 1, 2)$。在某些地图中，电梯可能无法连接所有楼层，此时输入中将不会包含某些边。
• 自动扶梯有两种使用方式：
  • 从 A 移动到 B（正向）：成本为 $1$ 米，因为我们只需走几步，然后自动扶梯就会带我们过去。
  • 从 B 移动到 A（反向）：成本为 B 和 A 之间欧几里得距离的 $3$ 倍。

最短步行路径必须仅使用这些连接。所有地点之间至少有一条路径相连。

输入格式

每个输入文件包含一个购物中心的地图和一系列查询。 第一行包含两个整数 $N$ ($N \le 200$) 和 $M$ ($N - 1 \le M \le 1000$)，分别表示地点的数量和连接的数量。地点编号从 $0$ 到 $N-1$。接下来的 $N$ 行，每行包含一个地点的楼层以及坐标 $x, y$。楼层之间的距离为 $5$ 米。另外两个坐标 $x$ 和 $y$ 以米为单位。 接下来的 $M$ 行包含地点之间的直接连接。每个连接由两个地点的标识符和移动类型（以下之一：walking、stairs、lift 或 escalator）定义。请根据上述说明检查每种类型的成本。同一楼层地点的类型为 walking。 下一行包含一个整数 $Q$ ($1 \le Q \le 1000$)，表示随后的查询数量。接下来的 $Q$ 行，每行包含两个地点 $a$ 和 $b$。我们想要得到从 $a$ 到 $b$ 的最短步行路径距离。

输出格式

对于每个查询，输出一行，包含从起点到终点的最短路径（以步行米数为单位），路径中的每个地点用空格分隔。

样例

样例输入 1

6 7
3 2 3
3 5 3
2 2 3
2 6 4
1 1 3
1 4 2
0 1 walking
0 2 lift
1 2 stairs
2 3 walking
3 4 escalator
5 3 escalator
4 5 walking
5
0 1
1 2
3 5
5 3
5 1

样例输出 1

0 1
1 0 2
3 4 5
5 3
5 3 2 0 1