Bessie uwięziona jest w trójkątnym labiryncie o $N$ rzędach, $1 \le N \le 1,000,000$. Poniżej trzy rzędy.

Rząd $i$ ma $2*i-1$ trójkątów, od lewej $(i,1)$, $(i,2)$ itd.

Może przejść do trójkątów o wspólnym boku, zwykle trzech. Z $(3,3)$ do $(3,2)$, $(3,4)$, $(4,4)$. Przejście trwa minutę.

FJ wie o uwięzieniu i śledzi iPhone: start drogi do wyjścia to ($Si,Sj$). Kocha bezgranicznie, chce najszybszego powrotu.

Jest $M$ wyjść w różnych miejscach, $1 \le M \le 10,000$, dowolne pozwala uciec. Po wejściu w trójkąt wyjścia jeszcze jedna minuta do opuszczenia labiryntu.

Znajdź minimalny czas $T$ minut i optymalne wyjście $(OUTi, OUTj)$. Przy równych $T$ wybierz najmniejszy rząd, przy równych rzędach mniejszą kolumnę.

Wejście

• Wiersz $1$: całkowite $N$, $M$ przez spację.

• Wiersz $2$: całkowite $Si$, $Sj$ przez spację.

• Wiersze $3..M+2$: wiersz $i+2$, dwie całkowite przez spację $Ei$, $Ej$, trójkąt wyjścia $i$.

Wyjście

• Wiersz $1$: całkowite $OUTi$, $OUTj$ przez spację.

• Wiersz $2$: jedna całkowita $T$.

Przykład

Wejście 1

4 2
2 1
3 5
4 4

Wyjście 1

4 4
4

Autor zadania: Ye Wang, 2009