题目描述

你有一些城市，城市之间用单向道路连接，道路不会重叠。我们在二维坐标系上用点来表示这些城市。

道路网络一开始只有两座城市以及连接他们的双向道路组成，连接两座城市的道路的长度就是他们的欧几里得距离。

你需要模拟整个城市网络的建立过程，支持两种操作：

• d X Y A B，在坐标 $(X,Y)$ 上新增一座城市（保证该点原来没有城市），并建立该城市到标号为 $A$ 和 $B$ 的双向道路。

• u A B，查询 $A$ 到 $B$ 的最短路。

城市 $1,2$ 在输入中固定，此后每增加一个城市，就赋予下一个自然数作为其标号。

输入格式

第一行两个整数，表示城市 $1$ 的坐标。

第二行两个整数，表示城市 $2$ 的坐标。

第三行一个整数 $N$，表示操作数量。

以下 $N$ 行，每行是两种操作的其中一个。

输出格式

对于所有 u 操作，你需要输出一个实数，表两个城市之间的最短路。（误差在 $0.1$ 内是允许的）。

6 4
10 4
9
d 6 7 2 1
u 1 2
u 3 2
d 10 2 1 2
u 3 4
d 12 7 2 4
u 5 3
u 4 5
u 1 5

4.000000
5.000000
7.000000
8.605551
5.385165
7.605551

1 1
3 8
10
d 8 2 1 2
u 2 1
d 2 9 1 3
u 1 4
d 4 7 3 4
u 4 3
d 6 1 5 4
u 6 5
d 0 0 4 6
u 7 3

7.280110
8.062258
9.219544
6.324555
18.439089

提示

• Subtask $1$（$21$ pts）：满足 $N\le 10^3$。

• Subtask $2$（$24$ pts）：所有类型为 u 的命令中的城市 A 相同。

• Subtask $3$（$55$ pts）：$1\le N\le 10^5,0\le X_1,X_2,Y_1,Y_2\le 10^6$。