Comfortable Cows Chain Reaction

Farmer Nhoj's field is modeled as a giant chessboard of square cells. Initially, the field is empty. Farmer Nhoj will add N cows one by one at distinct cells \((x_i,y_i)\) with \(0 \le x_i,y_i \le 1000\). A cow is said to be comfortable if it has exactly three neighbors in the four cardinal directions, i.e., if exactly three of the cells \((x_i+1,y_i)\), \((x_i-1,y_i)\), \((x_i,y_i+1)\), and \((x_i,y_i-1)\) are occupied by cows.

Whenever a cow becomes comfortable, the chain reaction forces Farmer Nhoj to add an extra cow in the only empty adjacent cell (the missing neighbor among the four). Note that the extra cows can be added anywhere on the plane (i.e. without the \(0 \ldots 1000\) restriction) and may in turn make other cows comfortable. Farmer Nhoj’s goal is to add the minimum number of extra cows so that, after processing all chain reactions, no cow (initial or extra) is comfortable.

Your task is: for each \(i=1,2,\dots,N\), when initially placing cows 1 through \(i\), determine the minimum number of extra cows added after simulating all chain reactions such that no cow is comfortable.

Note: If a cow is comfortable (i.e. has exactly three occupied adjacent cells), then exactly one extra cow is forced to be added at the only adjacent position that is unoccupied. This extra addition may create further comfort conditions and lead to cascading additions.

inputFormat

The first line contains a single integer \(N\) \((1 \le N \le 10^5)\), the number of cows initially placed.

The following \(N\) lines each contain two integers \(x_i\) and \(y_i\) \((0 \le x_i,y_i \le 1000)\), specifying the coordinates of the \(i\)th cow. All positions are distinct.

outputFormat

Output \(N\) lines. The \(i\)th line should contain the minimum number of extra cows that must be added to the field to ensure that no cow is comfortable after the first \(i\) cows are placed and the subsequent chain reactions have been processed.

sample

4
0 0
0 1
0 2
1 1

0
0
0
1