在浩瀚的银河系中，宇宙大帝统治着无数星系，但他不满足于现状，计划进一步扩展他的星际帝国。他决定在宇宙中的关键位置建立战略基地，从而增强对不同星系的控制。

在广阔的星系版图上，存在 n 个星际要塞，每个要塞的位置由其坐标 (x, y) 确定。为了最大化控制范围，大帝需要选择出从 1 到 n 中选出 k 个要塞，并在这些要塞之间建立一个新的指挥中心 P(x, y)​，以确保从指挥中心到这些要塞的曼哈顿距离之和最小。

曼哈顿距离：两个点 (a,b),(c,d) 的曼哈顿距离为 |a-c|+|b-d|。

你需要帮助大帝计算在不同选择方案下的最优指挥中心位置，使得他能够最有效地统治整个星域。

从文件 base.in 中读入数据。

第一行包含两个整数 n 和 k，分别表示星际要塞的数量和最大选择的要塞数量。

接下来的 n 行，每行包含两个整数，表示每个要塞的坐标 (x, y)。

输出到文件 base.out 中。

对于每个 t = 1 到 t = k，输出一个整数，表示在选择 t 个要塞时，最优指挥中心到这些要塞的最小曼哈顿距离之和。

【数据范围】

对于 100% 的数据：1 ≤ n，k ≤ 1000 ， xi,yi ≤ 10^9