Mê cung là một lưới ô vuông n×n, Minh có thể di chuyển giữa các ô, góc trên bên trái là (1,1), góc dưới bên phải (n,n) là đích. Trong mê cung, ngoài việc di chuyển một ô theo bốn hướng lên, xuống, trái, phải, còn có m cổng dịch chuyển hai chiều có thể sử dụng, mỗi cổng dịch chuyển có thể nối hai ô bất kỳ.

Hỏi độ dài đường đi ngắn nhất từ điểm xuất phát đến đích là bao nhiêu?

Vị trí ban đầu của Minh phân bố ngẫu nhiên đều trên tất cả các ô của mê cung, quy tắc di chuyển của cậu:

1. Tốn 1 bước để di chuyển một ô theo bốn hướng lên, xuống, trái, phải (không được vượt ra ngoài biên);

2. Nếu vị trí hiện tại có cổng dịch chuyển, tốn 1 bước để đi qua cổng dịch chuyển đến điểm dịch chuyển tương ứng.

Tính kỳ vọng của số bước ngắn nhất đi từ vị trí ban đầu ngẫu nhiên đến đích, kết quả giữ hai chữ số thập phân.

Dữ liệu vào

Dòng đầu tiên: hai số nguyên dương $n, m$

$m$ dòng tiếp theo: mỗi dòng bốn số nguyên dương $x_{i1}, y_{i1}, x_{i2}, y_{i2}$, biểu thị hai ô được nối bởi cổng dịch chuyển thứ $i$

Dữ liệu ra

Một dòng gồm một số thực, biểu thị kỳ vọng của số bước ngắn nhất (giữ hai chữ số thập phân)

Ví dụ

Input

2 1
1 1 2 2

Output

0.75

Ghi chú

Giải thích ví dụ

Đích là $(2,2)$:

• $(2,2)$: số bước = 0

• $(1,2)$, $(2,1)$: mỗi ô đi 1 bước là đến đích

• $(1,1)$: qua cổng dịch chuyển, 1 bước là đến đích

Tổng số bước: $0+1+1+1=3$

Kỳ vọng: $\frac{3}{2 \times 2} = 0.75$

Quy mô và ràng buộc dữ liệu

• 20% dữ liệu: $n,m \le 20$

• 100% dữ liệu: $n,m \le 2000$; mọi tọa độ đều không vượt quá $n$