题目描述

Kozak Vus 是一名大学生。在第一学期，他面临 $n$ 门科目和 $m$ 周的学习。Vus 提前知道了所有的作业，为了方便，他估算了它们的难度。他制作了一张 $n \times m$ 的表格，其中第 $i$ 门科目在第 $j$ 周需要完成一份难度为 $a_{i, j}$ 的作业。注意，整张表格中所有的难度值均两两不同。

Vus 将一周的难度定义为该周所有科目作业难度的总和。

Vus 假期没有休息够，所以他希望至少学期初不要学得太累。幸运的是，今年学生被允许调整自己的学习计划。Vus 可以执行以下操作至多 $k$ 次：选择一门科目 $i$ 和不同的两周 $j_1$ 与 $j_2$，然后交换这门科目在这两周的作业。于是，在表格中，$a_{i, j_1}$ 与 $a_{i, j_2}$ 交换位置。

Vus 的目标是让第一周的难度尽可能小。如果有多种方式达到这一点，他希望让第二周的难度尽可能小。如果仍有多种方式，则让第三周的难度尽可能小，依此类推。

更形式化地，令 $b_j$ 为第 $j$ 周的难度：

Kozak Vus 希望使用不超过 $k$ 次操作，使得操作后每周难度构成的数组 $B = [b_1, b_2, \dots, b_m]$ 字典序最小。请帮助他找出这个数组。

输入格式

第一行包含三个整数 $n$、$m$、$k$（$1 \le n, m \le 1000$，$0 \le k \le 10^9$）—— 行数、列数以及最大操作次数。

接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{i,j}$（$1 \le a_{i,j} \le 10^6$，所有 $a_{i,j}$ 两两不同）—— 初始的表格。

输出格式

输出 $m$ 个整数 —— 经过不超过 $k$ 次操作后可以得到的字典序最小的列和数组。

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

12 17 16

3 4 2
9 1 7 4
2 8 3 10
5 6 11 12

8 18 21 31

提示

对于第一个样例：

由于 $k = 1$，至多可以执行一次操作。

初始的列和为：

$7 + 6 + 5 = 18$，

$1 + 8 + 2 = 11$，

$3 + 4 + 9 = 16$。

因此初始的和数组为 $[18, 11, 16]$。

为了得到字典序最小的数组，最优做法是在第一行执行一次操作，交换数字 $7$ 和 $1$。

交换后，表格变为：

第一行：$1\ 7\ 3$，

第二行：$6\ 8\ 4$，

第三行：$5\ 2\ 9$。

此时列和为：

$1 + 6 + 5 = 12$，

$7 + 8 + 2 = 17$，

$3 + 4 + 9 = 16$。

所得数组 $[12, 17, 16]$ 是在一次操作能够达到的所有方案中字典序最小的。

对于第二个样例：

初始的列和为：

$9 + 2 + 5 = 16$，

$1 + 8 + 6 = 15$，

$7 + 3 + 11 = 21$，

$4 + 10 + 12 = 26$。

初始的和数组为 $[16, 15, 21, 26]$。

在第一行执行一次操作，交换数字 $9$ 和 $1$，再执行第二次操作，仍然在第一行交换数字 $9$ 和 $4$。于是我们得到如下表格：

$1\ 4\ 7\ 9$

$2\ 8\ 3\ 10$

$5\ 6\ 11\ 12$

列和为 $[8, 18, 21, 31]$。

计分

• （$3$ 分）：$k = n \cdot m$；
• （$5$ 分）：$k = 1$，$n = 1$；
• （$11$ 分）：$n = 1$；
• （$13$ 分）：各行元素初始按降序排列；
• （$16$ 分）：$k \le 10$；
• （$11$ 分）：$m = 2$；
• （$16$ 分）：$n, m \le 100$；
• （$25$ 分）：无额外限制。

翻译由 DeepSeek V4 Pro 完成