The Manhattan peninsula is one of the five boroughs of New York City. The borough is famous for its skyscrapers, broad avenues, the financial center Wall Street and the many yellow taxis that drive around the district. The streets of Manhattan are laid out in a rectangular grid by the Commissioners' Plan of 1811. The area is intersected by avenues (running north and south) and streets (running east and west).

Manhattan Commissioner's Plan
Manhattan Commissioners' Plan

Consider a rectangular $$s \times a$$ grid that represent part of Manhattan covering $$s$$ streets and $$a$$ avenues. Taxis can refuel at a number of petrol stations located at various intersections. Whenever a taxi is close to running out of gasoline, its driver can read the coordinates of the closest petrol station from his GPS. Due to bad programming, however, there is a bug in the GPS devices of the taxis. If there are multiple "closest" petrol stations at a given intersection, the GPS gets lost, which panics the driver who then causes a car crash. Such intersections are therefore called critical points.


In Manhattan, an intersection on a rectangular $$s \times a$$ grid is always represented as a tuple $$(x, y)$$, where $$x, y \in \mathbb{N}$$, $$0 \leq x < s$$ and $$0 \leq y < a$$. The intersection at the top left corner of the grid therefore is at position $$(0, 0)$$, and the intersection at the bottom right corner is at position $$(s-1, a-1)$$. This is also the representation of the intersections as they are used in this exercise.


In the example $$10\times 10$$ grid that is represented in the following interactive Python session, the intersection at position $$(5,0)$$ is an example of a critical point, since there are two petrol stations at Fourth Avenue that are both at distance 4 from the intersection $$(5,0)$$.

>>> manhattanDistance((3, 5), (7, 9))
>>> manhattanDistance((12, 5), (3, 16))

>>> critical((4, 3), [(1, 8), (4, 3), (6, 3), (6, 5)])
>>> critical((7, 4), [(1, 8), (4, 3), (6, 3), (6, 5)])

>>> manhattan(10, 10, [(1, 8), (4, 3), (6, 3), (6, 5)])