Crossroads#3041
In the country of Quadroland, the land is represented by an N\times N square. The coordinate system used by its inhabitants places the bottom-left corner of the square at and the top-right corner at (N, N). Within this square, there are cities, each located at integer coordinates. The people of Quadroland travel only along paths parallel to the coordinate axes. To facilitate faster travel to neighboring countries, the government plans to construct two high-speed highways. These highways must be perpendicular to each other and parallel to the coordinate axes, each connecting two opposite sides of the square.
The distance from a city to the highways is defined as the distance from the city to the nearest of the highways. The government wishes to place the highways to minimize the maximum distance from any city to the nearest highway.
Write a program that, given the side length of the square and the locations of the cities, finds the optimal maximum distance and the placement of the highways.
The first line contains two integers: (1 \leq N \leq 1000000) and (1 \leq K \leq 40000) — the side length of the square and the number of cities, respectively.
The next lines each contain two integers — the coordinates of the cities (ranging from to ).
Output a single line with three integers: the optimal maximum distance from the most distant city to the nearest highway, and the coordinates of the intersection point of the highways (the crossroads). If there are several optimal answers, output any of them.
Example 1