Ước mơ của Tuân là trở thành tỉ phú để mua cho Uyên một hòn đảo. Trong giấc mơ đó, Tuân đặt tên hòn đảo là đảo NTDU. Trên hòn đảo đó, Tuân sẽ trang bị mọi tiện nghi để Uyên cảm thấy mình như một nữ hoàng thực sự. Một trong số những tiện nghi cần thiết nhất là hệ thống internet và truyền hình để em trai và chị gái có thể nói chuyện với nhau ở mọi nơi trên hòn đảo.

Để thực hiện kế hoạch phủ sóng hòn đảo, Tuân đã xây dựng \(n\) trạm thu phát sóng. Mỗi trạm thu phát sóng có bán kính hoạt động giống nhau là \(r\) và có thể nhận tín hiệu từ các trạm thu khác trong tầm hoạt động của nó. Nói cách khác, trạm \(A\) và \(B\) được kết nối khi và chỉ khi \(AB \leq r\). Để mua thiết bị thu phát có bán kính \(r\), Tuân cần bỏ ra chi phí là \(X * r\) với \(X\) là hằng số cho trước. Tuân cũng có một lựa chọn khác là sử dụng dây ngầm nối trực tiếp 2 trạm thu phát bất kỳ, mỗi đường dây sẽ tốn chi phí là \(Y\) đồng.

Tuân cần kết hợp hai loại kết nối trên để đảm bảo tất cả các trạm thu phát có thể được kết nối với nhau (trực tiếp hoặc gián tiếp). Tìm chi phí nhỏ nhất Tuân cần bỏ ra để chinh phục Uyên (trong mơ). Tuân muốn bạn trả lời câu hỏi với \(q\) truy vấn \((X, Y)\).

Input

• Dòng đầu tiên chứa hai số tự nhiên \(n, q \ (n, q \leq 2000)\)
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i, y_i \ (|x_i|, |y_i| \leq 10^5)\) tương ứng với tọa độ của trạm thu phát sóng thứ \(i\). Không có hai trạm thu nào có cùng tọa độ.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X, Y \ (0 \leq X, Y \leq 10^9)\) tương ứng với một truy vấn.

Output

Với mỗi truy vấn, in ra một dòng là chi phí nhỏ nhất Tuân cần bỏ ra để chinh phục chị gái. Kết quả được chấp nhận nếu sai số không vượt quá \(10^{-6}\).

Ví dụ

Input 1

4 2
0 0
0 5
5 0
10 10
1 3
10 10000

Output 1

8.0000000000
111.8033988750

Input 2

3 2  
0 0
0 5
5 0
10 1
0 10

Output 2

2.0000000
0

Giới hạn

• \(20 \%\) số test có \(X = 10^9, Y \leq 10^6\) và \(q \leq 10\).
• \(20 \%\) số test có \(Y = 10^9\) và \(q \leq 10\).
• \(30 \%\) số test có \(q \leq 10\).
• \(30 \%\) số test còn lại không có điều kiện gì thêm.

Giải thích

Trong truy vấn 1 của test ví dụ 1, Tuân chọn \(r = 5\) và chọn nối dây giữa 2 trạm \((0, 5)\) và\((10, 10)\). Chi phí bỏ ra là \(X * r + Y * 1 = 8\). Trong hình dưới, đường nối liền biểu thị đường dây ngầm, và đường gạch nối biểu thị sự kết nối thông qua thiết bị thu phát vô tuyến.

Trong truy vấn 1 của test ví dụ 2, Tuân chọn \(r = 0\) (không đặt trạm thu phát), và đặt hai đường dây ngầm nối trạm 1-3 và 1-2. Chi phí là \(2Y = 2\).