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