Let Them Slide

题意翻译

给定 $n$ 个大小不同的数组与一个 $n$ 行 $w$ 列的表格。第 $i$ 个数组放置在第 $i$ 行中。你可以任意次横向滑动任意行中的数组，但要保证对于每行中数组的第一个元素在表格中的下标 $(i,pos_i)$ 都有 $1 \leq pos_i \leq w-length_i+1$。 对于每一列，请求出滑动后这一列的元素可以取得的最大和。若某一位置上无元素，视其值为 $0$。 图中从左到右显示了对于第 $1$ 列、第 $2$ 列、第 $3$ 列，取得该列最大和的情况。

题目描述

You are given $ n $ arrays that can have different sizes. You also have a table with $ w $ columns and $ n $ rows. The $ i $ -th array is placed horizontally in the $ i $ -th row. You can slide each array within its row as long as it occupies several consecutive cells and lies completely inside the table. You need to find the maximum sum of the integers in the $ j $ -th column for each $ j $ from $ 1 $ to $ w $ independently. Optimal placements for columns $ 1 $ , $ 2 $ and $ 3 $ are shown on the pictures from left to right.Note that you can exclude any array out of a column provided it remains in the window. In this case its value is considered to be zero.

输入输出格式

输入格式

The first line contains two integers $ n $ ( $ 1 \le n \le 10^{6} $ ) and $ w $ ( $ 1 \le w \le 10^{6} $ ) — the number of arrays and the width of the table. Each of the next $ n $ lines consists of an integer $ l_{i} $ ( $ 1 \le l_{i} \le w $ ), the length of the $ i $ -th array, followed by $ l_{i} $ integers $ a_{i1}, a_{i2}, \ldots, a_{il_i} $ ( $ -10^{9} \le a_{ij} \le 10^{9} $ ) — the elements of the array. The total length of the arrays does no exceed $ 10^{6} $ .

输出格式

Print $ w $ integers, the $ i $ -th of them should be the maximum sum for column $ 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 

说明

Illustration for the first example is in the statement.