Flowers

Bees are among the most important animals for pollinating flowers. A bee swarm uses a precise rule to decide which flowers to visit.

There are N flowers on a square flowerbed. The sides of the flowerbed are parallel to the coordinate axes, and two opposite corners are (0, 0) and (M, M). Each flower is represented by a point inside the flowerbed.

The swarm chooses one flower as its base camp, and all bees gather there. Then four bees move straight upward, downward, leftward, and rightward. Each bee keeps moving until it meets another flower or reaches the boundary of the flowerbed, then stops.

After all four bees stop, form the axis-aligned rectangle that passes through all four stopping coordinates. Every flower strictly inside this rectangle is pollinated. Flowers on the boundary of the rectangle are not pollinated.

Given the coordinates of all flowers, compute for each flower, in input order, how many flowers are pollinated when that flower is chosen as the base camp.

The first line contains the size M of the flowerbed. (2 <= M <= 1,000,000)

The second line contains the number of flowers N. (1 <= N <= 300,000)

Each of the next N lines contains the coordinates x and y of one flower. (0 < x, y < M)

No two flowers have the same coordinates.

For each flower, output on its own line the number of flowers pollinated when that flower is chosen as the base camp, in input order.