꽃

꽃가루받이에 가장 중요한 역할을 하는 동물 중 하나는 벌이다. 벌은 정교한 기준에 따라 어떤 꽃을 방문할지 정한다.

정사각형 화단 위에 꽃이 N개 있다. 화단의 변은 좌표축과 평행하며, 서로 마주 보는 두 꼭짓점의 좌표는 (0, 0)과 (M, M)이다. 각 꽃은 화단 안의 한 점으로 나타낸다.

벌 떼는 꽃 하나를 베이스 캠프로 정하고 모두 그곳에 모인다. 그다음 네 마리의 벌이 각각 위, 아래, 왼쪽, 오른쪽으로 곧게 이동한다. 각 벌은 다른 꽃을 만나거나 화단의 경계에 도착할 때까지 이동한 뒤 멈춘다.

네 마리 벌이 모두 멈추면, 벌들이 멈춘 네 좌표를 모두 지나고 변이 좌표축과 평행한 직사각형을 만든다. 이 직사각형의 내부에 있는 꽃은 모두 수분된다. 직사각형의 경계 위에 있는 꽃은 수분되지 않는다.

모든 꽃의 좌표가 주어졌을 때, 각 꽃을 베이스 캠프로 선택했을 때 수분되는 꽃의 수를 입력 순서대로 구하라.

첫째 줄에 화단의 크기 M이 주어진다. (2 <= M <= 1,000,000)

둘째 줄에 꽃의 개수 N이 주어진다. (1 <= N <= 300,000)

다음 N개 줄에는 각 꽃의 좌표 x와 y가 주어진다. (0 < x, y < M)

같은 좌표에 두 꽃이 있는 경우는 없다.

각 꽃에 대해, 그 꽃을 베이스 캠프로 선택했을 때 수분되는 꽃의 수를 한 줄에 하나씩 입력 순서대로 출력한다.