La distancia manhatthan de un punto ~(x, y)~ y otro ~(a, 0)~ es ~|x-a|+y~.

Se puede dividir en dos casos, se puede buscar el punto ~(x, y)~ más cerca de ~(a, 0)~ tal que ~x \leq a~, y lo mismo para ~x \geq a~, y la respuesta será el más cerca de ellos.

En el primer caso la expresión sería ~a - x + y~, como ~a~ es constante podemos buscar el punto que minimice ~-x+y~ y tenga ~x \leq a~, con un fenwick tree.

En el segundo caso la expresión sería ~x - a + y~, como ~-a~ es constante podemos buscar el punto que minimice ~x+y~ y tenga ~x \geq a~, con otro fenwick tree.

Complejidad ~O(n\log{n})~.

Otra posible solución sería, mantener un sqrt descomposition, y en cada bloque llevar la menor línea que entra desde la izquierda, la menor que entra desde la derecha, y para el bloque al que pertenece el punto updatearlo y hacer las queries con fuerza bruta, los detalles de esta solución se dejan como ejercicio al lector.