描述

给出 \(M\) 个区间 [\(l_i\), \(r_i\)]
定义区间 [\(l_1\), \(r_1\)] 和区间 [\(l_2\), \(r_2\)] 的距离为 \(min_{i=l_1}^{r_1} min_{j=l_2}^{r_2} \left | i-j \right |\)
求与这 \(M\) 个区间距离和最小的区间

输入

第一行两个正整数N, M
接下来M行，每行两个正整数 \(l_i\), \(r_i\)

输出

输出一行三个整数
分别为最小的距离和和对应区间的左端点、右端点
如有对应的区间有多个，输出左端点最小的，若仍有多个，输出右端点最小的
输出的区间需满足 \(1\leq l\leq r\leq N\)

样例

输入

5 2
1 5
1 4

输出

0 1 1

范围

40% \(N\leq 400\), \(M\leq 300\)
60% \(N\leq 5000\), \(M\leq 3000\)
100% \(N\leq 10^8\), \(M\leq 3\ast 10^5\), \(1\leq l_i\leq r_i\leq N\)

限制

1s
32M