Crossroads
In the country of Quadroland, the land is represented by an N×N square grid. The coordinate system used by its inhabitants places the bottom-left corner of the square at (0, 0) and the top-right corner at (N, N). Within this grid, there are K cities, each situated at a point with integer coordinates. The people of Quadroland travel 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 aligned with the coordinate axes, each spanning from one side of the square to the opposite side.
The goal is to minimize the maximum distance from any city to the nearest highway. The government aims to position the highways such that this maximum distance is minimized.
Your task is to write a program that, given the side length of the square and the locations of the cities, determines the optimal maximum distance and the placement of the highways.
Input
The first line contains two integers: N (1 ≤ N ≤ 1000000) and K (1 ≤ K ≤ 40000) - representing the side length of the square and the number of cities, respectively. The next K lines each contain two integers, indicating the coordinates of the cities (ranging from 0 to N).
Output
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 multiple optimal solutions, you may output any one of them.