시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB289947.368%

문제

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

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

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

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

입력

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

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

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

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

출력

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

예제 입력 1

3
4
1 2
2 2
2 1
1 1

예제 출력 1

1
1
1
1

예제 입력 2

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

예제 출력 2

3
5
3
5
3
3
5
W3sicHJvYmxlbV9pZCI6IjMxMTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFmNDMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWY0M1x1Yzc1OCBcdWMyMThcdWJkODRcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5MTFcdWM2OTRcdWQ1NWMgXHVjNWVkXHVkNTYwXHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWIzZDlcdWJiM2NcdWM3NDAgXHViYzhjXHVjNzc0XHViMmU0LiBcdWJjOGNcdWM3NDAgXHViOWU0XHVjNmIwIFx1YzgxNVx1YWQ1MFx1ZDU1YyBcdWFjZmNcdWM4MTVcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YzViNFx1YjVhNCBcdWFmNDNcdWM3NDQgXHVjMjE4XHViZDg0XHVkNTc0XHVjNTdjIFx1ZDU2MFx1YzljMCBcdWFjYjBcdWM4MTVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDY1NFx1YjJlOCBcdWM3MDRcdWM1ZDAgXHVhZjQzXHVjNzc0IE5cdWFjMWMgXHVjNzg4XHViMmU0LiBcdWQ2NTRcdWIyZThcdWM3NTggXHViY2MwXHVjNzQwIFx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NThcdWJhNzAsIFx1YzU5MSBcdWIwNWQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAoMCwwKSwgKE0sTSlcdWM3NzRcdWIyZTQuIFx1YWY0M1x1Yzc0MCBcdWQ2NTRcdWIyZTggXHVjNzA0XHVjNzU4IFx1YzgxMFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmM4YyBcdWI1YmNcdWIyOTQgXHViY2EwXHVjNzc0XHVjMmE0IFx1Y2VhMFx1ZDUwNFx1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVhZjQzXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWM4MTVcdWQ1NWMgXHViMmU0XHVjNzRjLCBcdWFjNzBcdWFlMzBcdWM1ZDBcdWMxMWMgXHViYWE4XHViNDUwIFx1YmFhOFx1Yzc3OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgXHViYzhjIFx1YjEyNFx1YjljOFx1YjlhY1x1YWMwMCBcdWFjMDFcdWFjMDEgXHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzY3Y1x1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHViYzhjXHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWFmNDNcdWM3NDQgXHViOWNjXHViMDk4XHVhYzcwXHViMDk4IFx1ZDY1NFx1YjJlOFx1Yzc1OCBcdWFjYmRcdWFjYzRcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTYwXHViNTRjXHVhZTRjXHVjOWMwIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHViYzhjXHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWJhNDhcdWNkOTggXHViMmU0XHVjNzRjXHVjNWQwIFx1YmM4YyBcdWIxMjRcdWI5YzhcdWI5YWNcdWFjMDAgXHViYTQ4XHVjZDk4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWJhYThcdWI0NTAgXHVkMWI1XHVhY2ZjXHVkNTU4XHViMjk0IFx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMCwgXHVhZGY4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWY0M1x1Yzc0NCBcdWJhYThcdWI0NTAgXHVjMjE4XHViZDg0XHVkNTVjXHViMmU0LiBcdWFjYmRcdWFjYzRcdWM3NTggXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFmNDNcdWM3NDAgXHVjMjE4XHViZDg0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZjQzXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWJhYThcdWI0NTAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWY0M1x1Yzc0NCBcdWJjYTBcdWM3NzRcdWMyYTQgXHVjZWEwXHVkNTA0XHViODVjIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjMjE4XHViZDg0XHVkNTU4XHViMjk0IFx1YWY0M1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDY1NFx1YjJlOFx1Yzc1OCBcdWQwNmNcdWFlMzAgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTSAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFmNDNcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZjQzXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyB4XHVjNjQwIHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7IHgsIHkgJmx0OyBNKTxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVhZjQzXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHVhYzAwXHVjOWMwXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1YWY0M1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWRmOCBcdWFmNDNcdWM3NDQgXHViY2EwXHVjNzc0XHVjMmE0IFx1Y2VhMFx1ZDUwNFx1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NWMgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzIxOFx1YmQ4NFx1ZDU1OFx1YjI5NCBcdWFmNDNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTE1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUENFTElDRSIsImRlc2NyaXB0aW9uIjoiPHA+QmVlcywgYXMgd2UgYWxsIGtub3csIGhhdmUgYW4gaW1wb3J0YW50IHJvbGUgaW4gcG9sbGluYXRpbmcgZmxvd2Vycy4gSXQgaXMgbGVzcyBrbm93biB0aGF0IGJlZXMgaGF2ZSBhbiBhd2t3YXJkbHkgcHJlY2lzZSBwcm90b2NvbCBmb3IgY2hvb3Npbmcgd2hpY2ggZmxvd2VycyB0byBwb2xsaW5hdGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBOIGZsb3dlcnMgb24gYSBtZWFkb3cuIFRoZSBtZWFkb3cgaXMgYSBzcXVhcmUgb24gdGhlIHBsYW5lIHdpdGggb3Bwb3NpdGUgY29ybmVycyBpbiAoMCwgMCkgYW5kIChNLCBNKSwgYW5kIHNpZGVzIHBhcmFsbGVsIHRvIHRoZSBjb29yZGluYXRlIGF4ZXMuIEZsb3dlcnMgYXJlIHBvaW50cyBpbnNpZGUgdGhlIG1lYWRvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBzd2FybSBvZiBiZWVzIGNob29zZXMgc29tZSBmbG93ZXIgYXMgdGhlaXIgYmFzZSBjYW1wIGFuZCBnYXRoZXJzIGFyb3VuZCBpdC4gRm91ciB3YXJyaW9yIGJlZXMgdGhlbiB0YWtlIG9mZiwgb25lIGluIGVhY2ggb2YgdGhlIGZvdXIgY2FyZGluYWwgZGlyZWN0aW9uczogdXAsIGRvd24sIGxlZnQgYW5kIHJpZ2h0LiBXYXJyaW9yIGJlZXMgc3RvcCB3aGVuIHRoZXkgZW5jb3VudGVyIGFub3RoZXIgZmxvd2VyIG9yIHJlYWNoIHRoZSBlZGdlIG9mIHRoZSBtZWFkb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSByZWN0YW5nbGUgZm9ybWVkIGJ5IHRoZSBmb3VyIHdhcnJpb3IgYmVlcyB3aXRoIHNpZGVzIHBhcmFsbGVsIHRvIHRoZSBjb29yZGluYXRlIGF4ZXMgaXMgdGhlIGFyZWEgdGhlIGJlZXMgd2lsbCBwb2xsaW5hdGUuIEZsb3dlcnMgb24gdGhlIGVkZ2Ugb2YgdGhpcyByZWN0YW5nbGUgd2lsbCBub3QgYmUgcG9sbGluYXRlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHRoZSBjb29yZGluYXRlcyBvZiBhbGwgZmxvd2VycywgZm9yIGVhY2ggZmxvd2VyIGNhbGN1bGF0ZXMgdGhlIHRvdGFsIG51bWJlciBvZiBwb2xsaW5hdGVkIGZsb3dlcnMgaWYgdGhhdCBmbG93ZXIgaXMgY2hvc2VuIGFzIHRoZSBiYXNlIGNhbXAuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyICgyICZsZTsgTSAmbGU7IDEgMDAwIDAwMCksIHRoZSBkaW1lbnNpb24gb2YgdGhlIG1lYWRvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAzMDAgMDAwKSwgdGhlIG51bWJlciBvZiBmbG93ZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgeCBhbmQgeSAoMCAmbHQ7IHgsIHkgJmx0OyBNKSwgdGhlIGNvb3JkaW5hdGVzIG9mIGEgZmxvd2VyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5ObyB0d28gZmxvd2VycyB3aWxsIHNoYXJlIHRoZSBzYW1lIHBhaXIgb2YgY29vcmRpbmF0ZXMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZmxvd2VyLCBvdXRwdXQgdGhlIG51bWJlciBvZiBwb2xsaW5hdGVkIGZsb3dlcnMgaWYgdGhhdCBmbG93ZXIgaXMgY2hvc2VuIGFzIHRoZSBiYXNlIGNhbXAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=