题目描述

国家 X 是一个边长为 $N$ 的正方形。它的左下角坐标为 $(0,0)$，右上角坐标为 $(N,N)$。

国家中有 $K$ 个城市，位于正方形内互不相同的整点处，包括边界上的点。城市大小忽略不计，视为点。

国家 X 的居民只能沿着水平线和竖直线移动，这些线与正方形边界的交点坐标均为整数。

政府计划修建一条水平高速公路和一条竖直高速公路，它们都要连接正方形的一对相对边，并且经过整点坐标。

一个城市到水平高速公路的距离，定义为该城市到这条水平线的竖直距离。类似地，一个城市到竖直高速公路的距离，定义为该城市到这条竖直线的水平距离。

一个城市到两条高速公路的距离，定义为它到较近的那条高速公路的距离。

政府希望选择这两条高速公路的位置，使所有城市到两条高速公路的最大距离尽可能小。

请编写程序 highways，根据正方形大小和城市位置，求出最优距离以及高速公路的位置。

输入格式

第一行输入两个正整数 $N$ 和 $K$，分别表示正方形边长和城市数量。

接下来 $K$ 行，每行输入两个整数 $x,y$，表示一个城市的坐标。

输出格式

输出一行三个整数，依次表示：

1. 最小可能的最大距离；
2. 两条高速公路交点的 $x$ 坐标；
3. 两条高速公路交点的 $y$ 坐标。

如果存在多个最优解，输出任意一个即可。

数据范围

• $1 \le N \le 1\,000\,000$；
• $1 \le K \le 1\,000\,000$；
• 每个城市坐标满足 $0 \le x,y \le N$；
• 所有城市位置互不相同；
• 在 $20\%$ 的测试中，$N \le 1000, K \le 100$。

样例

输入

5 3
1 2
2 4
4 1

输出

1 2 2

样例说明

图中展示了三个城市，以及经过 $x=2$ 和 $y=2$ 的两条高速公路。该方案下所有城市到最近高速公路的最大距离为 $1$。