Farmer John's pasture can be represented as a huge 2D grid of cells (a huge chessboard). Initially, the pasture is empty.
Farmer John will add N (1≤N≤10
5) cows to the pasture one by one. The i-th cow occupies a cell (x
i,y
i) that is different from the cells occupied by all other cows (0≤x
i, y
i≤1000).
A cow is said to be "comfortable" if she has exactly three other cows horizontally and vertically. Farmer John wants to count how many cows are comfortable in his pasture. For each i in the interval 1…N, print the total number of cows that are comfortable after the i-th cow is added to the pasture.
Input:
The first line contains a single integer N. Each of the following N lines contains two space-separated integers indicating the (x,y) coordinates of the cow's cell. It is guaranteed that all cells are distinct.
Output:
The i-th line of the output should contain the total number of cows that are comfortable after adding the i-th cow to the pasture.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
8
0 1
10
1 1
1 2
2 1
2 2
3 1
3 2 |
0
0
0
1
0
0
1
2 |
After the first 4 cows are added, the cow in cell (1,1) is comfortable.
After adding the first 7 cows, the cow in cell (2,1) is comfortable.
After adding the first 8 cows, the cow in cells (2,1) and (2,2) is comfortable. |