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

문제

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

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

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

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

입력

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

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

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

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

출력

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

예제 입력 1

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

예제 출력 1

3
5
3
5
3
3
5
W3sicHJvYmxlbV9pZCI6IjMxMTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFmNDMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWY0M1x1Yzc1OCBcdWMyMThcdWJkODRcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5MTFcdWM2OTRcdWQ1NWMgXHVjNWVkXHVkNTYwXHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWIzZDlcdWJiM2NcdWM3NDAgXHViYzhjXHVjNzc0XHViMmU0LiBcdWJjOGNcdWM3NDAgXHViOWU0XHVjNmIwIFx1YzgxNVx1YWQ1MFx1ZDU1YyBcdWFjZmNcdWM4MTVcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YzViNFx1YjVhNCBcdWFmNDNcdWM3NDQgXHVjMjE4XHViZDg0XHVkNTc0XHVjNTdjIFx1ZDU2MFx1YzljMCBcdWFjYjBcdWM4MTVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDY1NFx1YjJlOCBcdWM3MDRcdWM1ZDAgXHVhZjQzXHVjNzc0IE5cdWFjMWMgXHVjNzg4XHViMmU0LiBcdWQ2NTRcdWIyZThcdWM3NTggXHViY2MwXHVjNzQwIFx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NThcdWJhNzAsIFx1YzU5MSBcdWIwNWQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAoMCwwKSwgKE0sTSlcdWM3NzRcdWIyZTQuIFx1YWY0M1x1Yzc0MCBcdWQ2NTRcdWIyZTggXHVjNzA0XHVjNzU4IFx1YzgxMFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmM4YyBcdWI1YmNcdWIyOTQgXHViY2EwXHVjNzc0XHVjMmE0IFx1Y2VhMFx1ZDUwNFx1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVhZjQzXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWM4MTVcdWQ1NWMgXHViMmU0XHVjNzRjLCBcdWFjNzBcdWFlMzBcdWM1ZDBcdWMxMWMgXHViYWE4XHViNDUwIFx1YmFhOFx1Yzc3OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgXHViYzhjIFx1YjEyNFx1YjljOFx1YjlhY1x1YWMwMCBcdWFjMDFcdWFjMDEgXHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzY3Y1x1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHViYzhjXHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWFmNDNcdWM3NDQgXHViOWNjXHViMDk4XHVhYzcwXHViMDk4IFx1ZDY1NFx1YjJlOFx1Yzc1OCBcdWFjYmRcdWFjYzRcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTYwXHViNTRjXHVhZTRjXHVjOWMwIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHViYzhjXHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWJhNDhcdWNkOTggXHViMmU0XHVjNzRjXHVjNWQwIFx1YmM4YyBcdWIxMjRcdWI5YzhcdWI5YWNcdWFjMDAgXHViYTQ4XHVjZDk4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWJhYThcdWI0NTAgXHVkMWI1XHVhY2ZjXHVkNTU4XHViMjk0IFx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMCwgXHVhZGY4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWY0M1x1Yzc0NCBcdWJhYThcdWI0NTAgXHVjMjE4XHViZDg0XHVkNTVjXHViMmU0LiBcdWFjYmRcdWFjYzRcdWM3NTggXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFmNDNcdWM3NDAgXHVjMjE4XHViZDg0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZjQzXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWJhYThcdWI0NTAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWY0M1x1Yzc0NCBcdWJjYTBcdWM3NzRcdWMyYTQgXHVjZWEwXHVkNTA0XHViODVjIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjMjE4XHViZDg0XHVkNTU4XHViMjk0IFx1YWY0M1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDY1NFx1YjJlOFx1Yzc1OCBcdWQwNmNcdWFlMzAgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTSAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFmNDNcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZjQzXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyB4XHVjNjQwIHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7IHgseSAmbHQ7IE0pPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWFmNDNcdWM3NzQgXHVhYzE5XHVjNzQwIFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVhZjQzXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhZGY4IFx1YWY0M1x1Yzc0NCBcdWJjYTBcdWM3NzRcdWMyYTQgXHVjZWEwXHVkNTA0XHViODVjIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjMjE4XHViZDg0XHVkNTU4XHViMjk0IFx1YWY0M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxMTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQQ0VMSUNFIiwiZGVzY3JpcHRpb24iOiI8cD5CZWVzLCBhcyB3ZSBhbGwga25vdywgaGF2ZSBhbiBpbXBvcnRhbnQgcm9sZSBpbiBwb2xsaW5hdGluZyBmbG93ZXJzLiBJdCBpcyBsZXNzIGtub3duIHRoYXQgYmVlcyBoYXZlIGFuIGF3a3dhcmRseSBwcmVjaXNlIHByb3RvY29sIGZvciBjaG9vc2luZyB3aGljaCBmbG93ZXJzIHRvIHBvbGxpbmF0ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIE4gZmxvd2VycyBvbiBhIG1lYWRvdy4gVGhlIG1lYWRvdyBpcyBhIHNxdWFyZSBvbiB0aGUgcGxhbmUgd2l0aCBvcHBvc2l0ZSBjb3JuZXJzIGluICgwLCAwKSBhbmQgKE0sIE0pLCBhbmQgc2lkZXMgcGFyYWxsZWwgdG8gdGhlIGNvb3JkaW5hdGUgYXhlcy4gRmxvd2VycyBhcmUgcG9pbnRzIGluc2lkZSB0aGUgbWVhZG93LiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIHN3YXJtIG9mIGJlZXMgY2hvb3NlcyBzb21lIGZsb3dlciBhcyB0aGVpciBiYXNlIGNhbXAgYW5kIGdhdGhlcnMgYXJvdW5kIGl0LiBGb3VyIHdhcnJpb3IgYmVlcyB0aGVuIHRha2Ugb2ZmLCBvbmUgaW4gZWFjaCBvZiB0aGUgZm91ciBjYXJkaW5hbCBkaXJlY3Rpb25zOiB1cCwgZG93biwgbGVmdCBhbmQgcmlnaHQuIFdhcnJpb3IgYmVlcyBzdG9wIHdoZW4gdGhleSBlbmNvdW50ZXIgYW5vdGhlciBmbG93ZXIgb3IgcmVhY2ggdGhlIGVkZ2Ugb2YgdGhlIG1lYWRvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHJlY3RhbmdsZSBmb3JtZWQgYnkgdGhlIGZvdXIgd2FycmlvciBiZWVzIHdpdGggc2lkZXMgcGFyYWxsZWwgdG8gdGhlIGNvb3JkaW5hdGUgYXhlcyBpcyB0aGUgYXJlYSB0aGUgYmVlcyB3aWxsIHBvbGxpbmF0ZS4gRmxvd2VycyBvbiB0aGUgZWRnZSBvZiB0aGlzIHJlY3RhbmdsZSB3aWxsIG5vdCBiZSBwb2xsaW5hdGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdGhlIGNvb3JkaW5hdGVzIG9mIGFsbCBmbG93ZXJzLCBmb3IgZWFjaCBmbG93ZXIgY2FsY3VsYXRlcyB0aGUgdG90YWwgbnVtYmVyIG9mIHBvbGxpbmF0ZWQgZmxvd2VycyBpZiB0aGF0IGZsb3dlciBpcyBjaG9zZW4gYXMgdGhlIGJhc2UgY2FtcC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgKDIgJmxlOyBNICZsZTsgMSAwMDAgMDAwKSwgdGhlIGRpbWVuc2lvbiBvZiB0aGUgbWVhZG93LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGZsb3dlcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyB4IGFuZCB5ICgwICZsdDsgeCwgeSAmbHQ7IE0pLCB0aGUgY29vcmRpbmF0ZXMgb2YgYSBmbG93ZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vIHR3byBmbG93ZXJzIHdpbGwgc2hhcmUgdGhlIHNhbWUgcGFpciBvZiBjb29yZGluYXRlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBmbG93ZXIsIG91dHB1dCB0aGUgbnVtYmVyIG9mIHBvbGxpbmF0ZWQgZmxvd2VycyBpZiB0aGF0IGZsb3dlciBpcyBjaG9zZW4gYXMgdGhlIGJhc2UgY2FtcC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d