Bessie 困在有 $N$ 列的三角迷宮中，$1 \le N \le 1,000,000$。下圖是三列迷宮：

第 $i$ 列有 $2*i-1$ 個三角形，從左依次編號 $(i,1)$、$(i,2)$ 等。

Bessie 可走到與目前三角形共邊的三角形（通常有三個）。例如從 $(3,3)$ 可到 $(3,2)$、$(3,4)$、$(4,4)$。每次移動到相鄰三角形耗時一分鐘。

FJ 得知牠被困，透過追蹤 iPhone 知道牠從 ($Si,Sj$) 開始尋找出口。FJ 對 Bessie 的愛無邊，想讓牠儘快回來。

迷宮各處有 $M$ 個出口，$1 \le M \le 10,000$，任何一個都可逃脫。進入出口三角形後，只需再一分鐘離開迷宮。

求離開迷宮的最短分鐘數 $T$，並報告所用最佳出口 $(OUTi, OUTj)$。多個出口都需 $T$ 分鐘時選列號最小的；最佳列相同時選行號較小的。

輸入格式

• 第 $1$ 行：以空格分隔的整數 $N$、$M$。

• 第 $2$ 行：以空格分隔的整數 $Si$、$Sj$。

• 第 $3..M+2$ 行：第 $i+2$ 行以兩個用空格分隔的整數 $Ei$、$Ej$ 給出出口 $i$ 所在的三角形。

輸出格式

• 第 $1$ 行：以空格分隔的整數 $OUTi$、$OUTj$。

• 第 $2$ 行：一個整數 $T$。

範例

輸入格式 1

4 2
2 1
3 5
4 4

輸出格式 1

4 4
4

題目作者：Ye Wang，2009