Party Conference: Counting Politicians' Affiliations

The president of the party in power is holding a conference at the party headquarters located at the cell \((0,0)\) on a two-dimensional grid. Each cell contains a politician except if it contains an obstacle. Other politicians live in the grid and will attend the conference if they can reach the headquarters in \(S\) steps or less using the shortest path. They can move one step at a time in one of the four directions: up, down, left, or right, but cannot step into a cell with an obstacle.

Furthermore, the president has observed that each time a politician moves one step, they switch their party affiliation. Assume every politician starts as a member of the party in power. Therefore, if the shortest path from a politician's cell to \((0,0)\) requires an even number of moves, they will maintain their affiliation with the ruling party, while an odd number of moves will cause them to be affiliated with the opposing party.

Your task is to compute the number of politicians that come to the conference as members of the party in power and as members of the opposition.

Input format: The first line contains two integers \(S\) and \(N\) where \(S\) denotes the maximum allowed steps and \(N\) denotes the number of obstacles. Each of the following \(N\) lines contains two integers \(x\) and \(y\) representing the coordinates of an obstacle. Note that obstacles can appear anywhere on the grid. Politics live on all cells that do not contain an obstacle.

Output format: Output two integers separated by a space: the first is the number of politicians arriving as members of the party in power (even number of steps) and the second is the number arriving as members of the opposition (odd number of steps).

The mathematical expression for the condition is: A cell \((x,y)\) will attend the conference if there exists a path from \((x,y)\) to \((0,0)\) in \(\le S\) steps. Each move toggles the affiliation, so the affiliation at arrival is determined by the parity of the minimum distance \(d\), where if \(d\) is even then the affiliation is the party in power and if odd then the opposition.

inputFormat

The first line of input contains two integers \(S\) and \(N\) separated by a space, where \(S\) is the maximum number of steps allowed, and \(N\) is the number of obstacles on the grid.

Each of the following \(N\) lines contains two integers \(x\) and \(y\), indicating the coordinates of an obstacle.

Note: The grid is conceptually infinite, but only cells that can be reached from \((0,0)\) in \(\le S\) steps are relevant.

outputFormat

Output two integers separated by a space. The first integer is the count of politicians who will attend the conference as members of the party in power (even number of moves), and the second is the count of those attending as members of the opposing party (odd number of moves).

sample

2 1
0 1

8 3