Bessie está atrapada en un laberinto triangular de $N$ filas, $1 \le N \le 1,000,000$. Abajo uno de tres filas.

La fila $i$ tiene $2*i-1$ triángulos, de izquierda a derecha $(i,1)$, $(i,2)$, etc.

Puede ir a los que comparten lado, normalmente tres. De $(3,3)$ a $(3,2)$, $(3,4)$, $(4,4)$. Cada paso toma un minuto.

FJ sabe que está atrapada y sigue su iPhone para conocer el inicio de su salida ($Si,Sj$). Su amor no tiene límites y quiere que vuelva lo antes posible.

Hay $M$ salidas dispersas, $1 \le M \le 10,000$, cualquiera permite escapar. Tras entrar en una, necesita un minuto más para salir del laberinto.

Halla el mínimo $T$ minutos y la salida óptima $(OUTi, OUTj)$. Si varias tardan $T$, menor fila; si empatan filas, menor columna.

Entrada

• Línea $1$: enteros $N$, $M$ separados por espacio.

• Línea $2$: enteros $Si$, $Sj$ separados por espacio.

• Líneas $3..M+2$: línea $i+2$, dos enteros separados por espacio $Ei$, $Ej$, ubicación del triángulo de salida $i$.

Salida

• Línea $1$: enteros $OUTi$, $OUTj$ separados por espacio.

• Línea $2$: un entero $T$.

Ejemplos

Entrada 1

4 2
2 1
3 5
4 4

Salida 1

4 4
4

Autor del problema: Ye Wang, 2009