Kozak Vus is a student at a university. In the first semester, he has subjects and 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 -th subject in the -th week he has to complete an assignment of difficulty a_{i, j}. Note that all difficulty values are pairwise distinct across the entire table.
Vus calls the 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 times: choose a subject 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 -th week:
Kozak Vus wants to apply no more than 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 , , (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 lines contain 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 integers — the lexicographically smallest array of column sums that can be obtained after no more than operations.
Example 1
Example 2
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 and .
After that, the table will look like this:
first row: ,
second row: ,
third row: .
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 and , then perform a second operation and swap the numbers and also in the first row. Then we obtain the following table:
The column sums are [8, 18, 21, 31].
( points): k=n\cdot m;
( points): k=1, n=1;
( points): n=1;
( points): the elements in the rows are initially sorted in descending order;
( points): k \le 10;
( points): m=2;
( points): n, m \le 100;
( points): no additional constraints.