시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

꽃의 수분에 있어서 가장 중요한 역할을 하는 동물은 벌이다. 벌은 매우 정교한 과정을 통해 어떤 꽃을 수분해야 할지 결정한다.

화단 위에 꽃이 N개 있다. 화단의 변은 축에 평행하며, 양 끝 꼭지점의 좌표는 (0,0), (M,M)이다. 꽃은 화단 위의 점으로 나타낸다.

벌 떼는 베이스 캠프로 사용할 꽃을 하나 정한 다음, 거기에서 모두 모인다. 그 다음, 벌 네마리가 각각 위, 아래, 왼쪽, 오른쪽으로 이동한다. 벌은 다른 꽃을 만나거나 화단의 경계에 도착할때까지 이동한다. 벌이 모두 멈춘 다음에 벌 네마리가 멈춘 좌표를 모두 통과하는 축에 평행한 직사각형을 만들고, 그 직사각형 내부에 있는 꽃을 모두 수분한다. 경계의 위에 있는 꽃은 수분하지 않는다.

꽃의 좌표가 모두 주어졌을 때, 각각의 꽃을 베이스 캠프로 사용한 경우에 수분하는 꽃의 수를 구하는 프로그램을 작성하시오.

입력

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

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

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

두 꽃이 같은 좌표를 가지는 경우는 없다.

출력

각각의 꽃에 대해서, 그 꽃을 베이스 캠프로 사용한 경우에 수분하는 꽃의 개수를 출력한다.

예제 입력

10
7
1 3
5 3
7 3
4 2
4 4
6 4
6 1

예제 출력

3
5
3
5
3
3
5

힌트