Reunión de torres
En los últimos días, todas las piezas que hay guardadas en el club de ajedrez están un poco inquietas. Parece ser que están cansadas de que los humanos las sobemos mientras dura la partida y luego las devolvamos a sus cajas oscuras y frías.
No tenemos muy claro cómo lo han hecho, pero las torres se han puesto de acuerdo y han decidido tener una reunión en el tablero de ajedrez que hay en la trastienda para tratar el asunto. Con la seguridad que da la oscuridad de la noche, han salido de sus cajas y han ido todas hacia ese tablero para verse. Pero han cometido un pequeño error: no han decidido en qué casilla coincidir, así que ahora está cada una en una celda distinta y tienen que decidir (a gritos…) dónde se ven. Obviamente es una reunión clandestina, por lo que quieren elegir la casilla que minimice la suma de las distancias recorridas por todas ellas, teniendo en cuenta que cada torre solo se mueve en horizontal o vertical.
Entrada
La entrada estará compuesta por distintos casos de prueba, cada uno ocupando varias líneas.
La primera línea de cada caso contiene dos números. El primero, N, indica el número de celdas en horizontal y vertical que tiene el tablero en el que se han reunido (2 ≤ N ≤ 10.000). El segundo indica el número T de torres que hay sobre él (2 ≤ T ≤ min(100.000, N×N)).
A continuación aparecerán T líneas con las coordenadas ocupadas por cada una de las torres. El primero indica la fila y el segundo la columna, siendo la coordenada 1 1 la esquina inferior izquierda. Se garantiza que, en el instante inicial, no hay más de una torre en la misma posición.
Salida
Por cada caso de prueba se escribirá la celda en la que se deben reunir para minimizar la suma de la distancia recorrida por todas las torres. Se utilizará el mismo formato que en la entrada: la fila y la columna separadas por un espacio en una única línea.
Si hay varias opciones posibles se dará la posición que esté más a la izquierda, es decir la que tenga un menor valor en la columna. Si sigue habiendo más de una respuesta, se dará la que esté más abajo, es decir la de menor fila. Se admite que la celda de reunión esté ya ocupada por una torre (que no tendrá que moverse).
Entrada de ejemplo
8 3 4 3 7 4 5 7 8 4 1 1 8 1 8 8 1 8
Salida de ejemplo
5 4 1 1