“天庭”是一个巨大的空间站。它由若干细长的圆柱形舱体组成。每个舱体的两端各有一个连接点。一个连接点可以连接多个舱体。

如果我们把连接点看作节点，把舱体看作边，那么空间站的结构可以看作一棵树。

与样例输入对应的空间站结构。

空间站的形状可以通过绕连接点旋转舱体来改变。在初始状态下，所有舱体的方向（从一端到另一端）都平行于三维坐标轴。舱体可以绕其任一端的连接点作为枢轴进行任意旋转，只要其最终方向仍然平行于坐标轴之一。注意，所有连接在另一端（直接或间接）的舱体也会同时旋转。你不需要担心舱体之间的碰撞或重叠。假设它们可以安全地“穿过”彼此。

给定空间站的初始形状以及后续的一系列旋转操作，你能求出两个给定连接点之间的欧几里得距离吗？

输入格式

第一行包含两个整数 $N$ 和 $Q$ ($2 \le N \le 10^5, 1 \le Q \le 10^5$)，分别表示连接点的数量和操作的数量。

接下来的 $N-1$ 行，每行包含三个整数 $u, v, w$ ($1 \le u, v \le N, u \neq v, 1 \le w \le 10^6$) 和两个字符，表示在连接点 $u$ 和连接点 $v$ 之间存在一个长度为 $w$ 的舱体。这两个字符是 “x+”、“x-”、“y+”、“y-”、“z+”、“z-” 之一，表示从连接点 $u$ 到连接点 $v$ 的舱体方向。保证给定的结构是一棵树。

接下来的 $Q$ 行，每行包含一个操作。操作有两种类型：旋转舱体和查询两个给定连接点之间的欧几里得距离。

第一种类型的操作描述如下：

1 u v axis degree

其中 $u$ 和 $v$ ($1 \le u, v \le N, u \neq v$) 是两个连接点，$axis$ 是 “x”、“y” 或 “z” 之一，$degree$ 是 90、180 或 270 中的一个整数。这意味着我们绕着穿过连接点 $u$ 且指向 $axis$ 正方向的直线作为枢轴，按照右手定则将连接连接点 $u$ 和连接点 $v$ 的舱体旋转 $degree$ 度。保证连接点 $u$ 和连接点 $v$ 由一个舱体连接。有关旋转的更多信息，请参见下图。

旋转操作：1 1 3 z 270

旋转操作：1 3 1 x 90

第二种类型的操作描述如下：

2 u v

这意味着你需要求出连接点 $u$ 和连接点 $v$ 之间的欧几里得距离 ($1 \le u, v \le N$)。

同样，你不需要担心任何碰撞或重叠。假设它们可以安全地“穿过”彼此。

输出格式

对于每个第二种类型的操作，输出一行包含该距离的结果。你的答案应具有小于 $10^{-9}$ 的绝对或相对误差。即，如果你的答案是 $a$，裁判的答案是 $b$，那么当满足 $\frac{|a - b|}{\max(1, |b|)} \le 10^{-9}$ 时，你的答案被接受。

样例

输入 1

5 10
2 1 1 y+
1 3 2 x-
3 4 3 z+
5 3 1 y-
2 2 3
2 2 5
1 1 3 z 270
2 2 3
2 2 5
1 3 1 x 90
2 4 2
2 1 4
2 5 5
2 5 2

输出 1

2.236067977499790
2.828427124746190
3.000000000000000
3.162277660168379
6.000000000000000
5.000000000000000
0.000000000000000
3.162277660168379

说明

请阅读在线题目以查看彩色图片。