← 返回题目列表

Codeforces · 1208/E

E. 让他们滑动

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

给你 $$$n$$$ 个可以有不同大小的数组。您还有一个包含 $$$w$$$ 列和 $$$n$$$ 行的表。第 $$$i$$$ 数组水平放置在第 $$$i$$$ 行中。您可以在其行内滑动每个数组,只要它占据多个连续的单元格并且完全位于表格内。

您需要独立找到从 $$$1$$$ 到 $$$w$$$ 的每个 $$$j$$$ 的第 $$$j$$$ 列中整数的最大和。

列 $$$1$$$、$$$2$$$ 和 $$$3$$$ 的最佳位置显示在图片中从左到右。

请注意,您可以将任何数组从列中排除,只要它保留在窗口中即可。在这种情况下,其值被认为为零。

输入

第一行包含两个整数 $$$n$$$ ($$$1 \le n \le 10^{6}$$$) 和 $$$w$$$ ($$$1 \le w \le 10^{6}$$$) - 数组的数量和表格的宽度。

接下来的 $$$n$$$ 行包含一个整数 $$$l_{i}$$$ ($$$1 \le l_{i} \le w$$$)、第 $$$i$$$ 数组的长度,后跟 $$$l_{i}$$$ 整数 $$$a_{i1}、a_{i2}、\ldots、 a_{il_i}$$$ ($$$-10^{9} \le a_{ij} \le 10^{9}$$$) — 数组的元素。

数组的总长度不超过$$$10^{6}$$$。

输出

打印 $$$w$$$ 整数,其中第 $$$i$$$ 应该是列 $$$i$$$ 的最大总和。

示例

输入 #1

3 3
3 2 4 8
2 2 5
2 6 3

输出 #1

10 15 16

输入 #2

2 2
2 7 8
1 -8

输出 #2

7 8

注意

第一个示例的说明在声明中。