Minimizing Maximum Delivery Distance

Kosta, a barbecue master, has opened N restaurants in Manhattan, labeled from 1 to N. Each restaurant C is located at a point \((X_C, Y_C)\) on the coordinate plane. The Manhattan distance between two restaurants A and B is defined as \(|X_A - X_B| + |Y_A - Y_B|\).

Kosta plans to purchase at most two modern machines for automated hamburger production. Each machine is installed in an existing restaurant, and every restaurant receives its hamburgers from the nearest restaurant that has a machine installed. Let \(D_C\) be the Manhattan distance from restaurant C to the nearest restaurant with a machine. Kosta wants to minimize the maximum of all \(D_C\), that is, minimize \(\max_{C} D_C\).

Your task is to compute the minimal possible value of \(\max_{C} D_C\) given the locations of the restaurants and the number of machines (either 1 or 2). Furthermore, you should output the best restaurant(s) where the machine(s) should be installed. Note that when 2 machines are purchased, they can both be installed at the same restaurant.

Note: Restaurants are 1-indexed.

inputFormat

The input begins with a line containing two integers N and M (M = 1 or 2), where N is the number of restaurants. The following N lines each contain two integers, representing the coordinates \(X_i\) and \(Y_i\) of the i-th restaurant.

N M
X_1 Y_1
X_2 Y_2
... 
X_N Y_N

outputFormat

Output two lines. The first line contains a single integer: the minimal possible maximum distance \(\max_{C} D_C\). The second line contains one or two integers representing the index (or indices) of the restaurant(s) where the machine(s) should be installed. If M = 1, output one index; if M = 2, output two indices (if both machines are installed in the same restaurant, output that index twice or simply output one instance as per your implementation, but here output the two indices).

sample

3 1
0 0
0 2
2 2

2
2