410073: GYM103937 H Competing Clubs

After a mostly peaceful week, UT Austin's CS week has devolved into an all-out turf war.

UT Austin can be seen as a $$$N \times N$$$ grid with $$$K$$$ clubs located at various (distinct) points.

Clubs patrol their turf by walking between edges in the $$$4$$$ cardinal directions. A club controls a cell of this grid if its path to that cell is shorter than all other clubs. In the case of ties, the club with the lowest index wins.

UTPC hasn't joined in yet, but rather than fight over land, we seek only to develop a rivalry with another club by positioning ourselves to take their land. Given that we're the last club to join, we won't win any tiebreakers.

Given the grid size and clubs, determine how much of that club's turf UTPC could take for each club.

Three numbers, $$$1 \leq N \leq 750$$$ and $$$1 \leq K \leq min(10^4,\frac{N^2}{2})$$$.

The next $$$K$$$ lines are a list of the $$$K$$$ club locations.

It is guaranteed that there will not be more than one club or building per cell.

$$$K$$$ lines, for each club, the amount of its turf UTPC could take.

4 3
1 2
2 3
3 2

2
4
2