Ước mơ của Lương là trở thành tỉ phú để mua cho Vy một hòn đảo. Trong giấc mơ đó, Lương đặt tên hòn đảo là đảo VH. Trên hòn đảo đó, Lương sẽ trang bị mọi tiện nghi để Vy 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 để anh trai và em 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, Lương đã 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 rr, Lương cần bỏ ra chi phí là \(X \times r\) với \(X\) là hằng số cho trước. Lương 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.

Lương 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 Lương cần bỏ ra để chinh phục Vy (trong mơ). Lương 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

• Số cách tìm được sau khi chia lấy số dư cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(X = 10^9 , Y \leq 10^6\) và \(q \leq 10\).
• Subtask \(2\) (\(20\%\) số điểm): \(Y = 10^9\) và \(q \leq 10\).
• Subtask \(3\) (\(30\%\) số điểm): \(q \leq 10\).
• Subtask \(4\) (\(30\%\) số điểm): không có điều kiện gì thêm.

Example

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

8.0000000000
111.8033988750

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

2.0000000
0