Đồng cỏ của Farmer Nhoj đượ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 Nhoj 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. Không may, những con bò quá thoải mái thường giảm sản lượng sữa, nên Farmer Nhoj muốn thêm bò cho đến khi không còn con nào, kể cả các con mới thêm, cảm thấy thoải mái. Tọa độ \(x\) và \(y\) của những con bò được thêm không nhất thiết nằm trong đoạn \(0\ldots1000\).

Với mỗi \(i\) trong đoạn \(1\ldots N\), giả sử ban đầu đồng cỏ chỉ có các bò \(1\ldots i\). Hãy tính số bò ít nhất Farmer Nhoj cần thêm để không còn con bò nào thoải má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ò.

Dữ liệu ra

Với mỗi \(i\) trong \(1\ldots N\), in số bò ít nhất Farmer Nhoj cần thêm trên một trong \(N\) dòng riêng biệt.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

9
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
4 1

0
0
0
1
0
0
1
2
4

Nguồn

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

Tác giả: Benjamin Qi.