某电子工厂正在设计一块大型电路板,该板子可以看作一个由单位方格组成的平面网格。
工厂将按顺序在网格上逐步放置 N 个电子元件,第 i 个元件放置在坐标为 (x_i, y_i) 的方格中。
在电路板上,一个已放置的电子元件被称为是“被激活的”,当且仅当它在水平和竖直四个方向上(即上、下、左、右)恰好有 3 个相邻的已放置元件(相邻指两个方格共享一条边)。
随着元件的逐个放置,原本处于激活状态的元件可能会因为邻居数量变为 4 而失去激活状态,而原本未激活的元件也可能因为邻居数量增加到 3 而进入激活状态。
请你编写程序,在每放置一个元件后,实时统计并输出当前电路板上所有处于“被激活”状态的元件数量。
第一行一个整数 N,表示元件的总数。
接下来 N 行,每行两个整数 x_i 和 y_i,表示第 i 个元件放置的位置。
共 N 行,第 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
10 5 5 5 4 5 6 4 5 6 5 4 4 4 6 6 4 6 6 7 5
0 0 0 1 0 0 1 2 4 3
18 10 10 10 11 11 10 10 9 9 10 11 11 9 11 10 12 11 9 9 9 11 12 9 12 10 8 12 10 8 10 12 11 11 8 12 9
0 0 0 1 0 0 1 0 1 3 4 6 5 4 3 2 3 3
对于 100\% 的数据,满足 1 \leq N \leq 10^5,0 \leq x_i, y_i \leq 1000,所有元件的位置互不相同。
| 测试点编号 | N |
|---|---|
| 1 \sim 3 | 1 \le N \le 400 |
| 4 \sim 10 | 1 \le N \le 10^5 |