Kosta is planning on buying two at most modern machines for automatic making of burgers. Each machine is going to be implemented in an existing restaurant and the burgers will be delivered by car every morning to all the remaining restaurants. Of course, when the burgers are delivered to the remaining restaurants, they are delivered from the closest restaurant that owns a burger machine. For restaurant C, we define DC as the distance between restaurant C to its closest restaurant that owns a burger machine. It’s bad to keep the burgers in the car for too long, so Kosta wants to pick the locations for the burger machines in a way that the furthest restaurant gets the freshest burgers as soon as possible. In other words, we want the maximum value DC to be the minimum possible.

Write a programme that will, based on the locations of restaurants and the number of machines that Kosta is going to buy (one or two), calculate the minimum possible value D so that we can implement the burger machines in existing restaurants, and that the distance to all the remaining restaurants is at most D. Additionally, your programme should determine the optimal locations of the machines. If Kosta is buying two machines, it is allowed to implement both machines in the same restaurant.

입력

• The first line of input contains the integer K (1 <= K <= 2), the number of burger machines Kosta is going to buy.
• The second line of input contains the integer N, the number of restaurants (limitations for number N depend on number K, see section “Scoring”).
• Each of the following N lines contains integers XK and YK (0 <= XK, YK <= 10^6) - coordinates of an individual restaurant. There will not exist two restaurants on the same location.

출력

• The first line of output must contain an integer - the required minimum possible value D.
• The second line of output must contain K space-seperated integers - restaurants in which Kosta is implementing the machines

입출력 예

입력

2
5
1 1
2 3
5 10
4 6
7 12

출력

5
1 3

입력

2
10
3 6
1 4
4 1
4 7
4 10
3 8
3 10
6 7
5 1
2 10

출력

5
1 3

입력

1
10
3 10
6 1
5 7
0 4
2 7
2 0
9 2
4 1
3 6
1 4

출력

10
3

출처:CROATIAN HIGH SCHOOL COMPETITION