Đồng cỏ của Farmer John được xem là một lưới lớn gồm các ô vuông hai chiều. Ban đầu, đồng cỏ trống.

Farmer John lần lượt thêm \(N\) con bò vào đồng cỏ (\(1\le N\le10^5\)). Con bò thứ \(i\) chiếm một ô \((x_i,y_i)\) khác mọi ô đã có bò (\(0\le x_i,y_i\le1000\)).

Một con bò được gọi là "thoải mái" nếu có đúng ba con bò khác kề với nó theo phương ngang hoặc dọc. Farmer John muốn đếm số bò thoải mái trong trang trại. Với mỗi \(i\) trong đoạn \(1\ldots N\), hãy cho biết tổng số bò thoải mái sau khi thêm con bò thứ \(i\).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên, cách nhau bởi dấu cách, là tọa độ \((x,y)\) của ô có một con bò. Bảo đảm mọi ô này đôi một khác nhau.

Dữ liệu ra

Dòng thứ \(i\) chứa tổng số bò thoải mái sau khi thêm \(i\) con bò đầu tiên vào đồng cỏ.

Phân nhóm

• Các test 1-4 thỏa mãn \(N\le400\).
• Các test 5-12 không có ràng buộc bổ sung.

Ví dụ

8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2

0
0
0
1
0
0
1
2

Nguồn

USACO 2021 February Contest, Bronze - Comfortable Cows: https://usaco.org/index.php?page=viewproblem2&cpid=1108

Tác giả: Benjamin Qi.