우체국 관할 구역

M×M 크기의 격자 지도 위에 N개의 우체국이 있다. 각 우체국은 (x, y) 좌표에 위치한다.

격자의 각 칸은 맨해튼 거리(|x1-x2| + |y1-y2|)가 가장 가까운 우체국의 관할에 속한다. 거리가 같으면 번호가 작은 우체국의 관할로 한다.

각 우체국이 관할하는 칸의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 격자 크기 M과 우체국 수 N이 공백으로 구분되어 주어진다. (1 <= M <= 100, 1 <= N <= 50)
둘째 줄부터 N개의 줄에 각 우체국의 좌표 x, y가 공백으로 구분되어 주어진다. (0 <= x, y < M)

출력

첫째 줄에 각 우체국(1번부터 N번까지)이 관할하는 칸의 수를 공백으로 구분하여 출력한다.

입출력 예시

입력 1

10 3
2 3
7 7
5 1

출력 1

38 39 23

입력 2

8 4
1 1
6 1
1 6
6 6

출력 2

16 16 16 16