GRAD

Time limit2sMemory limit256 MB

Summary

Cities join the road network one by one with two roads each, and each query asks the shortest road distance between two cities.

Level: Hard9 of 10
Topics: Shortest path, Graph, Dynamic programming, Geometry
Solved: No attempts yet

Problem

The road network has cities in the plane and roads as straight segments between pairs of cities. Roads may intersect, but you can switch roads only at the two cities that road connects. Road length is Euclidean distance.

Initially cities 1 and 2 are connected. Each step adds one city and connects it by two new roads to two existing cities A and B that are already directly connected.

Support commands:

d X Y A B: add a city at $(X,Y)$ and connect it to A and B.
u A B: print the shortest road distance between A and B.

Input

Coordinates of cities 1 and 2, then $N$ commands in the forms above. No two cities share coordinates.

Output

For each u command, print the distance on its own line. Absolute error at most $0.1$ from the official answer is accepted.

Examples2

Example 1

Input

Expected output

Example 2

Input

Expected output