给你 $$$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
注意
第一个示例的说明在声明中。