Do tuyển tin bạn nào cũng thích chơi điện tử nên thầy Tùng phải đặt gấp thuốc chống nghiện điện tử của Marisa.

Marisa có ~n~ lọ thuốc, mỗi lọ thuốc có dạng hình trụ có chiều cao là ~h~ và bán kính đáy là ~r~. Thuốc có dạng lỏng và coi như vỏ lọ thuốc không đáng kể.

~m~ bạn học sinh sẽ quyết định mỗi bạn sẽ uống một lượng thuốc giống nhau là ~X~. Lần lượt từng bạn sẽ chọn chính xác một lọ thuốc và uống một lượng ~X~ trong lọ nếu còn đủ. Để hiệu quả chống nghiện tốt nhất, ~X~ phải là lớn nhất, hãy giúp các bạn học sinh tìm giá trị này để tất cả các bạn cùng nhau cai nghiện thành công.

Input: nhập vào từ file "CAINGHIEN.INP"

• Dòng đầu tiên gồm hai số nguyên ~n,m~.
• ~n~ dòng tiếp theo, mỗi dòng gồm hay số nguyên ~h,r~.

Output: ghi ra file "CAINGHIEN.OUT"

• In ra một số thực là đáp án của bài toán. Đáp án được coi là đúng khi chênh lệch với đáp án của hệ thống không quá ~10^{-6}~.

Điều kiện

• ~1 \le n \le 10^5~.
• ~1 \le m \le 10^9~.
• ~1 \le h,r \le 10^4~.

Ví dụ

Input:

3 4
3 2
1 1
2 3

Output:

18.849556

Giới hạn

• Subtask 1 (20% số điểm): ~m = 2~.
• Subtask 2 (30% số điểm): ~n,m \le 8~.
• Subtask 3 (50% số điểm): Không có giới hạn gì thêm.

Một câu chuyện rất dài... thầy đã xoá đi...

~n~ lon nước tăng lực của mrtee có độ phê lần lượt là ~a_1, a_2, \ldots, a_n~. Ban đầu, mrtee có sức hấp thụ dinh dưỡng là ~k~. Khi mrtee chuẩn bị uống một lon nước tăng lực, thầy sẽ phải vận nội công khiến cho ~k~ giảm đi ~1~ đơn vị. Và khi uống lon nước đó, mrtee sẽ được ~a_i \times k~ năng lượng. Mỗi lon chỉ được sử dụng tối đa ~1~ lần.

Giống như bao người khác, mrtee cũng có ngưỡng giới hạn cho sự tích trữ năng lượng của mình. Do đó, mrtee muốn đặt ra ~q~ câu hỏi. Trong mỗi câu hỏi, mrtee đưa ra một giá trị ~x~ và muốn bạn hãy tính xem mrtee có thể uống nhiều nhất bao nhiêu lon nước tăng lực sao cho tổng năng lượng thu được không vượt quá ~x~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, k~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.
• Dòng thứ ba chứa số nguyên dương ~q~.
• ~q~ dòng cuối cùng, mỗi dòng chứa một số nguyên dương ~x~ đại diện cho một câu hỏi của mrtee.

Output

• Với mỗi câu hỏi, in ra một số nguyên không âm là kết quả của câu hỏi đó.

Điều kiện

• ~1 \le n \le k \le 10^5~.
• ~1 \le q, a_i \le 10^5~.
• ~1 \le x \le 10^{16}~.

Subtask

• ~25\%~ số điểm: ~n, q \le 10~.
• ~25\%~ số điểm: ~n, q \le 10^3~.
• ~25\%~ số điểm: Tất cả lon nước có độ phê bằng nhau.
• ~25\%~ số điểm: Không có ràng buộc gì thêm.

Ví dụ

Input:

3 5
3 2 4
4
1 13 17 100

Output:

0
1
2
3

Đức là nhà vua trong tiểu vương quốc Hoàng Mai, ta có thể biểu diễn vương quốc này dưới dạng hệ trục tọa độ, anh ấy đang tìm kiếm vị trí để ~(u, v)~ để xây dựng ngôi biệt phủ của mình. Đức có ~n~ người yêu, người thứ ~i~ sống ở tọa độ ~(x_i, y_i)~. Vương Quốc của đức có luật giao thông rất kỳ lạ, trong một nước đi những người bạn gái của Đức chỉ có thể di chuyển giống như những quân hậu trên bàn cờ. Đức muốn ngôi biệt phủ tại tọa độ ~(u, v)~ của mình phải thỏa mãn điều kiện là mọi cô người yêu có thể di chuyển tới nó trong một nước đi. Hãy giúp Đức tìm một tọa độ ~(u, v)~ bất kỳ thỏa mãn nhé.

Input

• Dòng đầu chứa số nguyên dương ~n \leq 3 \times 10 ^ 5~
• ~n~ dòng, dòng thứ ~i~ chứa hai số nguyên ~x_i, y_i~ có giá trị tuyệt đối nhỏ hơn hoặc bằng ~10^9~

Output

• In ra tọa độ ~(u, v)~ bất kì thỏa mãn

Dữ liệu đảm bảo luôn tồn tại ~(u, v)~

Sample Input

2
2 2
1 1

Sample Output

1 3

Thành phố phép thuật nơi Rumia sống sắp mở một tuyến metro mới! Giống như mọi người dân trong thành phố, Rumia rất háo hức được thử tuyến metro này trong tương lai gần. Thành phố ấy có thể được coi là một cây có ~n~ đỉnh, trong đó tuyến metro được đặc trưng bởi hai số ~u, v~ ~(u < v)~, tức là tuyến metro đó sẽ sử dụng các đường đi là các cạnh trên đường đi ngắn nhất từ ~u~ đến ~v~, và mỗi thành phố mà nó đi qua sẽ được xây một nhà ga. Các đường đi đều có độ dài bằng ~1~.

Gọi ~f_{u, v}(x)~ là độ dài của đường đi ngắn nhất từ thành phố ~x~ đến một trong các thành phố có nhà ga metro thuộc tuyến metro ~u, v~. Ví dụ:

• ~f_{1, 4}(1) = f_{1, 4}(2) = f_{1, 4}(4) = 0~
• ~f_{1, 4}(3) = 1~ vì ở ~2~ có ga metro.
• ~f_{1, 4}(5) = 1~ vì ở ~4~ có ga metro.

Hãy tính ~\displaystyle \sum_{u = 1}^{n - 1} \sum_{v = u + 1}^{n}\sum_{x = 1}^{n} f_{u, v}(x)~, hay tổng ~\displaystyle \sum_{x = 1}^{n} f_{u, v}(x)~ với mọi cặp ~u, v~ ~(u < v)~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~.
• ~n - 1~ dòng sau, dòng thứ ~i~ chứa hai số nguyên dương ~u_i, v_i~ là thành phố có đường đi từ ~u_i~ đến ~v_i~.

Output

• In ra một số nguyên duy nhất là tổng cần tìm, chia lấy dư cho ~10^9 + 7~.

Subtasks

Trong tất cả các test, ~n \le 2 \times 10^5, u_i < v_i~.

• Subtask 1 ~(15\%)~: ~n \le 50~
• Subtask 2 ~(15\%)~: ~n \le 400~
• Subtask 3 ~(20\%)~: ~n \le 3000~
• Subtask 4 ~(20\%)~: ~u_i = i, v_i = i + 1~
• Subtask 5 ~(30\%)~: Không có giới hạn gì thêm.

Sample Input 1

5
1 2
2 3
2 4
4 5

Sample Output 1

27

Sample Input 2

6
1 2
2 3
3 4
4 5
5 6

Sample Output 2

70