← 返回题目列表

Codeforces · 514/D

D. R2D2 和机器人军队

中文机器翻译题面 查看原题

n 个机器人组成的军队排成一排。每个机器人由 m 个整数 a1, a2, ..., am 描述,其中 ai 是该机器人机制中第 i 个类型的细节数。 R2-D2 想要破坏最大长度的连续机器人序列。他有m件武器,第i件武器可以通过摧毁第i种类型的一个细节来影响军队中的所有机器人(如果机器人没有这种类型的细节,则不会发生任何事情)。

当一个机器人的所有细节都被摧毁时,它就被认为被摧毁了。 R2-D2 最多可以进行 k 次射击。 R2-D2 应该用什么类型的武器发射多少次子弹才能摧毁最大长度的连续机器人序列?

输入

第一行包含三个整数 n、m、k (1 ≤ n ≤ 105, 1 ≤ m ≤ 5, 0 ≤ k ≤ 109)——分别是机器人的数量、细节类型的数量和可用镜头的数量。

接下来的 n 行描述了机器人。每行包含 m 个整数 a1, a2, ..., am (0 ≤ ai ≤ 108),其中 ai 是相应机器人第 i 类的细节数。

输出

打印 m 个以空格分隔的整数,其中第 i 个数字是机器人为摧毁最大长度的连续机器人的子序列而应使用第 i 种类型的武器进行的射击次数。

如果有多个最优解,则打印其中任意一个。

没有必要精确地进行k次拍摄,拍摄次数可以更少。

示例

输入 #1

5 2 4
4 0
1 2
2 1
0 2
1 3

输出 #1

2 2

输入 #2

3 2 4
1 2
1 3
2 2

输出 #2

1 3

注意

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

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