Giải bài trực tuyến

Để chuẩn bị cho buổi giao lưu của cuộc thi HAOI năm nay, msn và Lola đã mua về một chiếc bánh pizza có hình thù đặc biệt. Chiếc bánh là một hình đa giác N đỉnh không tự cắt.

BB được giao nhiệm vụ sẽ cắt chiếc bánh này để chia cho mọi người. Để tăng thêm sự thú vị cho buổi giao lưu, BB đưa ra bài toán sau cho các bạn thí sinh. Nếu ta đặt chiếc bánh vào hệ tọa độ Đề các, mỗi nhát cắt sẽ là một đường thẳng song song với trục hoành.

BB muốn biết với mỗi nhát cắt như vậy, tổng độ dài của nhát cắt đi qua chiếc bánh là bao nhiêu. Một nhát cắt nếu đi trùng vào một cạnh của chiếc bánh phải tính cả độ dài của cạnh đó (xem trường hợp nhát cắt y = 3 trong test ví dụ). Người trả lời đúng nhiều nhất nhận được phần bánh to nhất, nhiều pho mát nhất, nhiều thịt bò nhất. beo_chay_so vốn rất ham ăn và rất muốn có phần bánh ngon nhất đó. Bạn hãy giúp beo_chay_so nhé.

Input

Dòng đầu tiên là hai số nguyên dương N và M trong đó M là số nhát cắt sẽ thực hiện.

Dòng thứ i trong N dòng tiếp theo ghi hai số nguyên X_i, Y_i là tọa độ của đỉnh thứ i của chiếc bánh.

Tọa độ đỉnh của chiếc bánh sẽ được liệt kê theo chiều kim đồng hồ.

Trên M dòng cuối, mỗi dòng có một số nguyên alpha trong đó đường thẳng y = alpha là đường thẳng thể hiện nhát cắt.

Output

Tương ứng với M dòng trong input, hãy ghi ra M số trên M dòng thể hiện tổng độ dài của nhát cắt thứ i đi qua chiếc bánh. Các số được ghi với độ chính xác ít nhất 6 chữ số sau dấu phẩy.

Example

Input:
8 4
0 0
0 3
1 3
3 1
3 3
4 1
3 0
1 1
0
1
2
3

Output:
0.000000
4.000000
2.500000
1.000000

Giới hạn:
1 ≤ N ≤ 1000 
1 ≤ M ≤ 50000
Các tọa độ có trị tuyệt đối không quá 105