Nông dân Don quan sát hàng rào bao quanh cánh đồng phẳng hình vuông cạnh \(N\) mét, với \(2\le N\le500000\). Một góc của hàng rào ở \((0,0)\), góc đối diện ở \((N,N)\); các cạnh song song với hai trục tọa độ.

Có một cọc rào ở mỗi góc và tại mỗi vị trí cách nhau một mét trên mỗi cạnh, tổng cộng \(4N\) cọc. Các cọc thẳng đứng và được coi là không có bán kính. Don muốn biết mình nhìn thấy được bao nhiêu cọc từ vị trí đang đứng trong hàng rào.

Trong cánh đồng có \(R\) tảng đá lớn, với \(1\le R\le30000\), che khuất một số cọc rào vì Don không đủ cao để nhìn qua chúng. Đáy mỗi tảng đá là một đa giác lồi có diện tích khác không, các đỉnh có tọa độ nguyên. Các tảng đá có mặt bên thẳng đứng; chúng không chồng lên nhau, không chạm nhau, không chạm Don và không chạm hàng rào. Don không đứng trong hay trên tảng đá, cũng không chạm hàng rào.

Hãy tính số cọc rào Don nhìn thấy. Nếu từ vị trí của Don, một đỉnh của tảng đá nằm thẳng hàng và che đúng một cọc rào thì cọc đó không nhìn thấy được.

Dữ liệu vào

Trong bản luyện tập, đọc dữ liệu từ đầu vào chuẩn. Tệp đầu vào trong đề gốc có tên boundary.in.

• Dòng đầu chứa hai số nguyên \(N,R\) cách nhau bởi dấu cách.
• Dòng tiếp theo chứa hai số nguyên là tọa độ \(X,Y\) của Don.
• Tiếp theo là mô tả của \(R\) tảng đá. Mỗi mô tả bắt đầu bằng một dòng chứa số nguyên \(p_i\), với \(3\le p_i\le20\), là số đỉnh của đáy tảng đá.
• \(p_i\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X,Y\) là tọa độ một đỉnh. Các đỉnh đôi một khác nhau và được cho theo chiều ngược kim đồng hồ. Các đỉnh liên tiếp có thể thẳng hàng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: số cọc rào Don nhìn thấy. Tệp đầu ra trong đề gốc có tên boundary.out.

Ràng buộc

Giới hạn thời gian: 1 giây CPU. Giới hạn bộ nhớ: 64 MiB.

Phân nhóm

Có 25 bộ dữ liệu, mỗi bộ tối đa 4 điểm. Mỗi bộ chỉ được điểm khi kết quả đúng; không có điểm thành phần trong một bộ dữ liệu.

Ví dụ

100 1
60 50
5
70 40
75 40
80 40
80 50
70 60

319

Nguồn

Đề gốc IOI 2003. Bảng tổng quan ngày 2.