Messenger

Time limit4sMemory limit128 MB

Summary

A unit-speed messenger runs straight from the first of two speed-1 polygonal routes to intercept the second, so minimize the carry time.

Level: Medium7 of 10
Topics: Geometry, Binary search
Solved: No attempts yet

Problem

Misha and Nadia each follow a polyline path in the plane at speed 1. Misha hands a package to a messenger at some point on his path. The messenger runs in a straight line to meet Nadia on her path and hands it over. The messenger also moves at speed 1. Find the minimum time from pickup to delivery.

Input

Two path descriptions are given. Each starts with $n$ points $(x_i,y_i)$ visited in order. Misha and Nadia start at the same time without stopping. Pickup must happen no later than when Misha finishes, and delivery no later than when Nadia finishes.

Output

Print the minimum delivery time with absolute error at most $10^{-3}$ or relative error at most $10^{-5}$ . Print impossible if delivery cannot happen.

Examples1

Example 1
Input
```
2
0 0
0 10
2
4 10
4 0
```
Expected output
```
4.00000
```