You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Farmer John 的草地可以被看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。初始时，草地上是空的。

Farmer John 将会逐一地将 $N$（$1\le N\le 10^5$）头奶牛加入到草地上。第 $i$ 头奶牛将会占据方格 $(x_i,y_i)$，不同于所有已经被其他奶牛占据的方格（$0\le x_i,y_i\le 1000$）。

一头奶牛被称为是「舒适的」，如果它水平或竖直方向上与恰好三头其他奶牛相邻。Farmer John 对他的农场上舒适的奶牛数量感兴趣。对 $1\ldots N$ 中的每一个 $i$，输出第 $i$ 头奶牛加入到草地上之后舒适的奶牛的数量。

输入格式

输入的第一行包含一个整数 $N$。以下 $N$ 行每行包含两个空格分隔的整数，表示一头奶牛所在的方格坐标 $(x,y)$。输入保证所有方格的坐标是不同的。

输出格式

输出的第 $i$ 行包含前 $i$ 头奶牛加入到草地上之后舒适的奶牛的数量。

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

提示

样例解释 1

在前四头奶牛加入之后，位于 $(1,1)$ 的奶牛是舒适的。

在前七头奶牛加入之后，位于 $(2,1)$ 的奶牛是舒适的。

在前八头奶牛加入之后，位于 $(2,1)$ 和 $(2,2)$ 的奶牛是舒适的。

测试点性质

• 测试点 $1-4$ 满足 $N\le 400$。
• 测试点 $5-12$ 没有额外限制。