Hôm nay bé Si làm bánh, mời những người bạn tới nhà để ăn mừng chức vô địch World Cup. Trên mặt phẳng tọa độ, chiếc bánh của bé Si được xem như là một đa giác điểm nguyên không tự cắt. Bé Rô - người bạn thân nhất của bé Si cũng tới nhà Si để ăn mừng thành tích của bạn mình.

Lúc này Rô nghĩ ra một thử thách để làm khó Si. Rô đưa ra \(q\) câu hỏi, với mỗi câu hỏi Rô sẽ đưa ra hai số nguyên \(l\) và \(r\), khi đó Rô sẽ dùng dao để cắt toàn bộ phần bánh bị giới hạn bởi hai đường thẳng \(x = l\) và \(x = r\) (có thể là không có phần bánh nào). Với mỗi câu hỏi như thế, Rô đố Si hãy tính diện tích phần bánh bị cắt ra. Lưu ý rằng mỗi câu hỏi được xem như một trường hợp riêng biệt và không ảnh hưởng đến nhau.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((3 \leq n \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5)\) là số đỉnh của đa giác và số truy vấn.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) \((|x_i|, |y_i| \leq 10^9)\) là toạ độ của đỉnh thứ \(i\). Điểm \((x_i, y_i)\) có cạnh nối tới đỉnh \((x_{i+1}, y_{i+1})\) với \(1 \le i < n\) và đỉnh \((x_n, y_n)\) có cạnh nối tới đỉnh \((x_1, y_1)\). Dữ liệu đảm bảo các đỉnh được cho lần lượt theo chiều kim đồng hồ.
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) \((-10^9 \leq l \leq r \leq 10^9)\) mô tả một truy vấn.

Output

• Gồm \(q\) dòng, mỗi dòng chứa một số thực là diện tích phần bánh bị cắt ra ứng với mỗi truy vấn.
• Đáp án của bạn được chấp nhận nếu chênh lệch tương đối không vượt quá \(10^{-6}\). Hay nói cách khác, nếu đáp án của bạn là \(a\) và đáp án của giám khảo là \(b\), đáp án của bạn được chấp nhận nếu \(\frac{|a - b|}{\max(1, b)} \leq 10^{-6}\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \le 10^3\), \(|x_i|, |y_i| \leq 5 \times 10^4\) và bánh luôn có dạng đa giác lồi.
• Subtask \(2\) (\(15\%\) số điểm): \(n \le 10^3\), \(|x_i|, |y_i| \leq 5 \times 10^4\) và các cạnh của bánh luôn song song với trục tọa độ.
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^3\), \(|x_i|, |y_i| \leq 5 \times 10^4\).
• Subtask \(4\) (\(15\%\) số điểm): Bánh luôn có dạng đa giác lồi.
• Subtask \(5\) (\(15\%\) số điểm): Các cạnh của bánh luôn song song với trục tọa độ.
• Subtask \(6\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

8 3
3 3
3 0
-2 0
-2 1
0 1
0 3
-2 3
0 6
-2 3
0 3
-3 0

Output

18.5
13.5
5.0

Note

Đây là hình minh họa: