문제
2차원 격자판 형태의 비어있는 포도밭이 있다.
포도밭의 주인은 총 N개의 포도를 심을 예정이며, 각 i번째 포도는 (xi, yi)칸에 심어질 것이다.
포도는 덩쿨식물이라 수직 수평으로 인접한 세 면에 다른 포도가 있어야 성장이 가능하다.
그러나 광합성을 위하여 한 면은 비어있어야한다.
포도밭의 주인은 각 i번째 포도를 심을 때 마다 성장 가능한 포도의 수가 몇개인지 알고싶다.
입력
첫 번째 줄에는 심어질 포도의 수 N (1≤N≤105)이 입력된다.
두 번째 줄부터 N줄에 걸쳐 i번째 포도가 심어질 위치 xi와 yi가(0≤xi,yi≤1000) 공백을 기준으로 주어진다 (중복되는 위치가 입력되지 않음이 보장된다).
출력
N줄에 걸쳐 i번째 줄에 i번째 포도가 심어진 후 성장가능한 포도의 수를 출력한다.
예제1
입력
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
힌트
출처
USACO 2021 February Bronze