CF514D.R2D2 and Droid Army

An army of n droids is lined up in one row. Each droid is described by m integers _a_1, _a_2, ..., a__m, where a__i is the number of details of the i-th type in this droid's mechanism. R2-D2 wants to destroy the sequence of consecutive droids of maximum length. He has m weapons, the i-th weapon can affect all the droids in the army by destroying one detail of the i-th type (if the droid doesn't have details of this type, nothing happens to it).

A droid is considered to be destroyed when all of its details are destroyed. R2-D2 can make at most k shots. How many shots from the weapon of what type should R2-D2 make to destroy the sequence of consecutive droids of maximum length?

一支由 $n$ 个机器人组成的军队排成一列。每个机器人用 $m$ 个整数 $a_1,\,a_2,\,\dots,\,a_m$ 描述，其中 $a_i$ 表示该机器人机构中第 $i$ 类零件的数量。R2-D2 希望摧毁一段长度最长的连续机器人序列。他拥有 $m$ 种武器，第 $i$ 种武器每次发射可对军队中所有机器人各摧毁一个第 $i$ 类零件（若某机器人不含该类零件，则对该机器人无影响）。

当一个机器人的所有零件均被摧毁时，该机器人即被视为被摧毁。R2-D2 最多可发射 $k$ 发子弹。为摧毁一段长度最长的连续机器人序列，R2-D2 应对每种武器各发射多少发子弹？

The first line contains three integers n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ 5, 0 ≤ k ≤ 109) — the number of droids, the number of detail types and the number of available shots, respectively.

Next n lines follow describing the droids. Each line contains m integers _a_1, _a_2, ..., a__m (0 ≤ a__i ≤ 108), where a__i is the number of details of the i-th type for the respective robot.

第一行包含三个整数 $n$、$m$、$k$（$1 \leq n \leq 10^5$，$1 \leq m \leq 5$，$0 \leq k \leq 10^9$），分别表示机器人的数量、零件类型的数量以及可用射击次数。

接下来的 $n$ 行描述各个机器人。每行包含 $m$ 个整数 $a_1,\,a_2,\,...,\,a_m$（$0 \leq a_i \leq 10^8$），其中 $a_i$ 表示该机器人所拥有的第 $i$ 类零件的数量。

Print m space-separated integers, where the i-th number is the number of shots from the weapon of the i-th type that the robot should make to destroy the subsequence of consecutive droids of the maximum length.

If there are multiple optimal solutions, print any of them.

It is not necessary to make exactly k shots, the number of shots can be less.

输出 m 个空格分隔的整数，其中第 i 个数表示机器人应使用第 i 种武器射击的次数，以摧毁最长的连续机器人子序列。

若存在多个最优解，输出任意一个即可。

不必恰好进行 k 次射击，实际射击次数可以少于 k。

In the first test the second, third and fourth droids will be destroyed.

In the second test the first and second droids will be destroyed.

在第一个测试中，第二、第三和第四台机器人将被摧毁。

在第二个测试中，第一和第二台机器人将被摧毁。