在 Bajtocki 国家剧院，话剧《Les Bitérables》即将首演。现在是时候准备演出所需的布景了。你从导演那里得到了关于如何为每一幕准备布景的指示。你的任务是制定一个计划，帮助在幕间以最快的速度更换布景。

对于每一幕，你都收到了舞台上需要放置布景元素的位置描述。由于这些布景元素非常相似（毕竟它们都是些“比特灌木”），因此只要放置在导演指定的位置，具体哪个元素放在哪个位置并不重要。我们还假设在同一幕中，两个布景元素永远不会出现在同一个位置。

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

遗憾的是，只有一名技术人员负责更换布景，而且所有布景元素都非常沉重，他一次只能搬运一个元素。在幕间（即两幕之间的休息时间）将一个布景元素从位置 $i$ 移动到位置 $j$ 需要花费 $|i - j|$ 秒，而除此之外，他在舞台上移动的时间可以忽略不计。请制定一个幕间布景更换计划，使得每次休息时间尽可能短。演出准备了充足的布景元素，因此如有需要，技术人员可以在后台找到所需的元素。

输入格式

输入的第一行包含两个整数 $n$ 和 $d$ ($2 \le n \le 500\,000$; $2 \le d \le 10^{12}$)，分别表示话剧的幕数和 Bajtocki 国家剧院舞台的长度。

接下来的 $n$ 行中，每一行包含一个非负整数 $s_i$，表示第 $i$ 幕所需的布景元素数量，随后是 $s_i$ 个递增的整数 $p_1, p_2, \dots, p_{s_i}$ ($0 < p_1 < p_2 < \dots < p_{s_i} < d$)，表示需要放置这些元素的位置。

所有 $s_i$ 值的总和不超过 $500\,000$。

输出格式

输出 $n - 1$ 行；第 $i$ 行应输出一个整数，表示在第 $i$ 幕和第 $i+1$ 幕之间完成所有必要更换以准备布景所需的最短时间（以秒为单位）。

样例

输入 1

3 10
2 4 7
3 3 6 8
1 5

输出 1

4
6

说明 1

在第一次幕间休息时，需要移动的元素：从位置 $4$ 移至位置 $3$，从位置 $7$ 移至位置 $6$，以及从后台（位置 $10$）移至位置 $8$。因此，完成更换所需的时间为 $4$ 秒。

在第二次幕间休息时，需要移动的元素：从位置 $3$ 移至后台（位置 $0$），从位置 $6$ 移至位置 $5$，以及从位置 $8$ 移至后台（位置 $10$）。因此，所需时间为 $6$ 秒。

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。