题目描述

题目译自 XXVIII Olimpiada Informatyczna – III etap Les Bitérables

字节国家剧院即将上演一出新剧《悲惨比特》（Les Bitérables）。现在是时候为演出准备舞台布景了。导演已经给了你关于每个幕所需布景的指示，你的任务是制定一个计划，让幕间更换布景的时间尽可能短。

对于每一幕，导演都会告诉你舞台上哪些位置需要放置布景元素。所有布景元素看起来都差不多，所以具体哪个元素放在哪个位置并不重要，只要是导演指定的位置即可。我们还假设，在同一幕中，两个布景元素绝不会出现在同一个位置。

并非每一幕都需要用到所有布景元素。未使用的元素需要存放在后台。舞台和后台可以看作一个区间 $[0, d]$，其中位置 $0$ 和 $d$ 是后台，其他整数位置是舞台上的位置。

遗憾的是，更换布景的工作只能由一名技术人员负责。由于布景元素都很重，他一次只能搬运一个。幕间休息时，将一个布景元素从位置 $i$ 搬到位置 $j$ 需要 $|i-j|$ 秒，而其他在舞台上的移动时间可以忽略不计。请你制定一个布景更换计划，让每次幕间休息的时间尽可能短。剧院已经准备了足够的布景元素，如果需要，技术人员可以在后台找到所需的元素。

输入格式

输入的第一行包含两个整数 $n$ 和 $d$ $(2 \leq n \leq 500000, 2 \leq d \leq 10^{12})$，分别表示剧目幕数和字节国家剧院舞台的长度。

接下来的 $n$ 行描述每一幕的布景需求，每行首先包含一个非负整数 $s_{i}$，表示第 $i$ 幕所需的布景元素数量，后面跟着 $s_{i}$ 个递增的整数 $p_{1}, p_{2}, \ldots, p_{s_{i}}$ $(0 < p_{1} < p_{2} < \ldots < p_{s_{i}} < d)$，表示需要放置布景元素的位置。

所有 $s_{i}$ 的总和不超过 $500000$。

输出格式

输出应包含 $n-1$ 行，第 $i$ 行输出一个整数，表示从第 $i$ 幕到第 $i+1$ 幕准备布景所需的最短时间（单位：秒）。

3 10
2 4 7
3 3 6 8
1 5

4
6

在第一次幕间休息时，需要移动布景元素：从位置 $4$ 到位置 $3$，从位置 $7$ 到位置 $6$，以及从后台（位置 $10$）到位置 $8$。总共需要 $4$ 秒。

在第二次幕间休息时，需要移动布景元素：从位置 $3$ 到后台（位置 $0$），从位置 $6$ 到位置 $5$，从位置 $8$ 到后台（位置 $10$）。总共需要 $6$ 秒。

样例 2

见附加文件下 [les1.in](file:les1.in) 和 [les1.out](file:les1.out)。

该样例满足 $n=3, d=5001$，第一幕和第三幕不需要布景元素，第二幕需要在位置 $1, 2, \ldots, 5000$ 放置 $5000$ 个布景元素；

样例 3

见附加文件下 [les2.in](file:les2.in) 和 [les2.out](file:les2.out)。

该样例满足 $n=5, d=10^{10}$，第 $j$ 幕需要在位置 $10^{5} \cdot i + 10^{4} \cdot j$（其中 $1 \leq i < 10^{5}, 1 \leq j \leq 5$）放置布景元素；

样例 4

见附加文件下 [les3.in](file:les3.in) 和 [les3.out](file:les3.out)。

该样例满足 $n=500000, d=10^{12}$，第 $i$ 幕在位置 $\left(i^{i} \bmod (d-1)\right)+1$ 放置一个布景元素（其中 $1 \leq i \leq 500000$）。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	对于每个 $i$，$s_{i} \leq 1$	$5$
$2$	对于每个 $i$，$s_{i} \leq 3$	$10$
$3$	$d \leq 7$	$12$
$4$	所有 $s_{i}$ 的总和不超过 $5000$	$27$
$5$	第 $i$ 幕若 $s_{i} > 0$，则 $p_{s_{i}} = p_{1} + s_{i} - 1$	$11$
$6$	无附加限制	$35$