PCELICE

문제

Bees, as we all know, have an important role in pollinating flowers. It is less known that bees have an awkwardly precise protocol for choosing which flowers to pollinate. 

There are N flowers on a meadow. The meadow is a square on the plane with opposite corners in (0, 0) and (M, M), and sides parallel to the coordinate axes. Flowers are points inside the meadow. 

A swarm of bees chooses some flower as their base camp and gathers around it. Four warrior bees then take off, one in each of the four cardinal directions: up, down, left and right. Warrior bees stop when they encounter another flower or reach the edge of the meadow. 

The rectangle formed by the four warrior bees with sides parallel to the coordinate axes is the area the bees will pollinate. Flowers on the edge of this rectangle will not be pollinated. 

Write a program that, given the coordinates of all flowers, for each flower calculates the total number of pollinated flowers if that flower is chosen as the base camp. 

입력

The first line contains an integer (2 ≤ M ≤ 1 000 000), the dimension of the meadow. 

The second line contains an integer N (1 ≤ N ≤ 300 000), the number of flowers. 

Each of the following N lines contains two integers x and y (0 < x, y < M), the coordinates of a flower. 

No two flowers will share the same pair of coordinates. 

출력

For each flower, output the number of pollinated flowers if that flower is chosen as the base camp. 

 

3
4
1 2
2 2
2 1
1 1

1
1
1
1

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

3
5
3
5
3
3
5