Bessie è intrappolata in un labirinto triangolare di $N$ righe, $1 \le N \le 1,000,000$. Sotto uno di tre righe.

Riga $i$ contiene $2*i-1$ triangoli, da sinistra $(i,1)$, $(i,2)$, ecc.

Passa ai triangoli con lato comune, spesso tre. Da $(3,3)$ a $(3,2)$, $(3,4)$, $(4,4)$. Ogni passaggio dura un minuto.

FJ sa che è intrappolata e segue l'iPhone: inizia il cammino d'uscita a ($Si,Sj$). Il suo amore è senza limiti, vuole il ritorno più rapido.

Ci sono $M$ uscite distribuite, $1 \le M \le 10,000$, qualunque consente di fuggire. Entrata nel triangolo d'uscita, serve solo un altro minuto per uscire.

Trova il minimo tempo $T$ minuti e uscita ottima $(OUTi, OUTj)$. A parità di $T$, minima riga; se righe uguali, minore colonna.

Input

• Riga $1$: interi $N$, $M$ separati da spazio.

• Riga $2$: interi $Si$, $Sj$ separati da spazio.

• Righe $3..M+2$: riga $i+2$, due interi separati da spazio $Ei$, $Ej$, triangolo d'uscita $i$.

Output

• Riga $1$: interi $OUTi$, $OUTj$ separati da spazio.

• Riga $2$: un intero $T$.

Esempi

Input 1

4 2
2 1
3 5
4 4

Output 1

4 4
4

Autore del problema: Ye Wang, 2009