题目描述

Kozak Vus is a student at a university. In the first semester, he has $n$ subjects and $m$ weeks of study ahead of him. Vus knows all the assignments in advance, and for convenience he has estimated their difficulty. He made a table of size $n \times m$, where for the $i$-th subject in the $j$-th week he has to complete an assignment of difficulty $a_{i, j}$. Note that all difficulty values are $\textbf{pairwise distinct}$ across the entire table.

Vus calls the $\textit{difficulty of a week}$ the total difficulty of the assignments from all subjects in that week.

Vus did not get enough vacation to rest, so he wants to avoid working too hard, at least at the beginning of the semester. Fortunately, this year students were allowed to adjust their study plan. Vus can perform the following operation at most $k$ times: choose a subject $i$ and two different weeks $j_1$ and $j_2$, then swap the assignments of this subject. Thus, in the table, the values $a_{i, j_1}$ and $a_{i, j_2}$ exchange places.

Vus's goal is to make the difficulty of the first week as small as possible. If there are several such ways, he wants to minimize the difficulty of the second week. If there are still several ways, he wants to minimize the difficulty of the third week, and so on.

More formally, let $b_j$ be the difficulty of the $j$-th week:

$$b_j = a_{1, j} + a_{2, j} + \dots + a_{n, j}$$

Kozak Vus wants to apply no more than $k$ operations so that the resulting array of weekly difficulties $B = [b_1, b_2, \dots, b_m]$ becomes lexicographically minimal. Help him find this array.

输入格式

The first line contains three integers $n$, $m$, $k$ ($1 \le n, m \le 1000$, $0 \le k \le 10^9$) --- the number of rows, the number of columns, and the maximum number of operations.

The next $n$ lines contain $m$ integers each, $a_{i,j}$ ($1 \le a_{i,j} \le 10^6$, all numbers $a_{i,j}$ are pairwise distinct) --- the initial table.

输出格式

Print $m$ integers --- the lexicographically smallest array of column sums that can be obtained after no more than $k$ operations.

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

提示

For the first sample:

Since $k = 1$, at most one operation can be performed.

The initial column sums are:

$7 + 6 + 5 = 18$,

$1 + 8 + 2 = 11$,

$3 + 4 + 9 = 16$.

So the initial sum array is $[18, 11, 16]$.

To obtain the lexicographically smallest array, it is best to perform an operation in the first row and swap the numbers $7$ and $1$.

After that, the table will look like this:

first row: $1\ 7\ 3$,

second row: $6\ 8\ 4$,

third row: $5\ 2\ 9$.

The column sums are:

$1 + 6 + 5 = 12$,

$7 + 8 + 2 = 17$,

$3 + 4 + 9 = 16$.

The resulting array $[12, 17, 16]$ is lexicographically smallest among all variants that can be obtained with one operation.

For the second sample:

The initial column sums are:

$9 + 2 + 5 = 16$,

$1 + 8 + 6 = 15$,

$7 + 3 + 11 = 21$,

$4 + 10 + 12 = 26$.

The initial sum array is $[16, 15, 21, 26]$.

Perform an operation in the first row and swap the numbers $9$ and $1$, then perform a second operation and swap the numbers $9$ and $4$ also in the first row. Then we obtain the following table:

$1\ 4\ 7\ 9$

$2\ 8\ 3\ 10$

$5\ 6\ 11\ 12$

The column sums are $[8, 18, 21, 31]$.

Scoring

• ($3$ points): $k=n\cdot m$;
• ($5$ points): $k=1$, $n=1$;
• ($11$ points): $n=1$;
• ($13$ points): the elements in the rows are initially sorted in descending order;
• ($16$ points): $k \le 10$;
• ($11$ points): $m=2$;
• ($16$ points): $n, m \le 100$;
• ($25$ points): no additional constraints.