Giải bài trực tuyến

Do nhà và trường của Zone nằm ở hai bên bờ của một con sông nên hàng ngày cậu phải đi đò qua sông để đi học. Zone cảm thấy rằng hành trình của ông lái đò là không tối ưu và Zone muốn tìm ra một đường đi tốt hơn.

Sau khi quan sát và đo đạc, Zone có thể biểu diễn được con sông bằng cách chỉ ra 2 bờ của nó. Mỗi bờ sông sẽ được biểu diễn bằng 1 đường gấp khúc và được xác định bằng tọa độ của các điểm trên đường gấp khúc đó như sau:

Đường gấp khúc biểu diễn bờ phía Đông của sông có N điểm, điểm thứ i có tọa độ (x_i, y_i).

Đường gấp khúc biểu diễn bờ phía Tây của sông có M điểm, điểm thứ j có tọa độ (u_j, v_j).

Biết rằng 2 bờ sông không có điểm chung và y_i < y_i+1 với mọi 1 ≤ i < N và v_j < v_j+1 với mọi 1 ≤ j < M.

Bạn hãy tìm 2 điểm A và B sao cho A nằm trên bờ Đông của con sông và B nằm trên bờ Tây của con sông và khoảng cách AB là nhỏ nhất.

Input

- Dòng đầu ghi 2 số nguyên dương N và M.

- Dòng thứ i trong N dòng tiếp theo ghi 2 số nguyên x_i, y_i.

- Dòng thứ j trong M dòng tiếp theo ghi 2 số nguyên u_j, v_j.

Output

- Gồm 1 dòng duy nhất ghi khoảng cách ngắn nhất tìm được

( Các số thực được ghi với độ chính xác 3 chữ số sau dấu phẩy )

Example

Input:
3 4
4 0
3 2
5 4
0 0
2 2
1 3
2 5

Output:
1.000

Giới hạn

• 2 ≤ M, N ≤ 1000
• |x_i|, |y_i|, |u_j|, |v_j| ≤ 10000