La ardilla viajera
La leyenda popular dice que en el libro Geografía escrito en el siglo I A.C., el geógrafo griego Estrabón dijo de la península ibérica que era tan frondosa que una ardilla podía cruzarla de sur a norte saltando de árbol en árbol sin tocar el suelo.
Parece ser que, en realidad, el bueno de Estrabón nunca aseguró tal cosa en su libro y, de hecho, hoy en día se cree que ni siquiera en aquellos tiempos la hazaña de la ardilla pudo ser cierta.
No obstante dejemos volar la imaginación por un momento y pensemos que en algún instante del pasado el número de árboles en el territorio de la península permitiera la aventura. Dado que hoy día no es posible realizarla, está claro que en algún momento del pasado se cortó el árbol que provocó la separación de la región del norte y la del sur en lo que a saltos de rama en rama se refiere.
Para simplificar un poco el problema, asumamos que el territorio es una región cuadrada de tamaño N×M en la que se sitúan árboles (que consideraremos de grosor 0) en posiciones (x, y). La tarea de la ardilla consiste en ir desde el árbol situado en la posición (0, 0) hasta la posición (N, M) (en ambas posiciones hay siempre un árbol). La ardilla es capaz de saltar de un árbol a otro si la distancia entre ambos no supera K unidades.
Los datos que tenemos del territorio son las posiciones de todos los árboles al principio de los tiempos y el orden en el que fueron cortados y debemos determinar la posición del árbol que, al ser cortado, hizo que la ardilla no pudiera atravesar la península de parte a parte sin pisar el suelo.
Entrada
Cada caso de prueba se compone de varias líneas. La primera de ellas tiene los números N, M, K y n (1 ≤ N, M ≤ 1.000; 1 ≤ K ≤ 10; 1 ≤ n ≤ 100.000), donde los tres primeros tienen el significado descrito más arriba y el último indica el número de árboles en el territorio (sin contar los situados en la esquina origen y destino de la ardilla que siempre están presentes).
A continuación aparece una línea por cada árbol con dos enteros x, y con la posición de cada uno. El orden en el que se dan es el mismo en el que después fueron cortados. Se garantiza que todas las posiciones están dentro del territorio y que no hay dos árboles en la misma ubicación.
Salida
Por cada caso de prueba se escribirá una única línea con la posición dentro del territorio del árbol que, cuando se cortó, provocó que las dos esquinas del territorio no fueran alcanzables para la ardilla.
Si la ardilla nunco pudo atravesar la península de parte a parte, se escribirá NUNCA SE PUDO.
Entrada de ejemplo
3 3 2 4 1 1 2 2 2 0 3 1 3 3 2 2 3 0 0 3
Salida de ejemplo
2 0 NUNCA SE PUDO