Bessie は $N$ 行、$1 \le N \le 1,000,000$、の三角迷路に閉じ込められています。下は三行の例です。

行 $i$ に $2*i-1$ 個の三角形があり、左から $(i,1)$、$(i,2)$ と呼びます。

今の三角形と辺を共有する三角形（通常三つ）へ行けます。$(3,3)$ からは $(3,2)$、$(3,4)$、$(4,4)$ へ。一移動は一分です。

FJ は閉じ込められたと知り、iPhone を追跡して出口探しの出発点 ($Si,Sj$) を知りました。愛は限りなく、最短で戻ってほしいのです。

迷路の各所に $M$ 出口、$1 \le M \le 10,000$、があり、どれでも脱出できます。出口三角形に入った後、もう一分で外に出ます。

最短時間 $T$ 分と最適出口 $(OUTi, OUTj)$ を求めてください。複数が $T$ 分なら最小行、行も同じなら小さい列を選びます。

入力

• 行 $1$：空白区切り整数 $N$、$M$。

• 行 $2$：空白区切り整数 $Si$、$Sj$。

• 行 $3..M+2$：行 $i+2$ に出口 $i$ の三角形を表す空白区切り二整数 $Ei$、$Ej$。

出力

• 行 $1$：空白区切り整数 $OUTi$、$OUTj$。

• 行 $2$：整数 $T$ 一つ。

入出力例

入力 1

4 2
2 1
3 5
4 4

出力 1

4 4
4

問題作成者：Ye Wang、2009