Problem
El pasto del granjero John se puede representar como una enorme cuadrícula de celdas en 2D (un enorme tablero de ajedrez). Inicialmente, el pasto está vacío.
El granjero John agregará N (1≤N≤10
5) vacas al pasto una por una. La i-ésima vaca ocupa una celda (x
i,y
i) que es diferente de las celdas ocupadas por todas las demás vacas (0≤x
i, yi≤1000).
Se dice que una vaca está "cómoda" si tiene exactamente otras tres vacas horizontal y verticalmente. El granjero John quiere contar cuántas vacas están cómodas en su pasto. Para cada i en el intervalo 1…N, imprima el número total de vacas que están cómodas después de agregar la i-ésima vaca al pasto.
Entrada:
La primera línea contiene un único número entero N. Cada una de las siguientes N líneas contiene dos números enteros separados por espacios que indican las coordenadas (x, y) de la celda de la vaca. Se garantiza que todas las celdas son diferentes.
Salida:
La línea i-ésima de la salida debe contener el número total de vacas que están cómodas después de agregar la vaca i-ésima al pasto.
Ejemplos
| # |
Entrada |
Salida |
Explicación |
| 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 |
Después de agregar las primeras 4 vacas, la vaca en la celda (1,1) está cómoda.
Después de agregar las primeras 7 vacas, la vaca en la celda (2,1) está cómoda.
Después de agregar las primeras 8 vacas, la vaca en las celdas (2,1) y (2,2) está cómoda. |