Background

Translated from XXVIII Olimpiada Informatyczna - Stage III Les Bitérables.

d1t2。

Problem Description

There are $t$ moments. At moment $i$, a configuration $p_1, p_2, \dots, p_{s_i}$ is given, meaning that within the interval $(0, d)$ on the number line, items exist at and only at positions $p_1, p_2, \dots, p_{s_i}$.

At position $0$ and position $d$, there are infinitely many items.

You may pay a cost of $1$ to move one item one position to the left or one position to the right.

For each pair of adjacent moments, ask for the minimum total cost needed to transform the previous configuration into the next configuration.

Input Format

The first line contains two positive integers $n, d$.

The next $n$ lines each describe the configuration at one moment. Each line starts with a non-negative integer $s_i$, followed by $s_i$ positive integers $p_1, p_2, \dots, p_{s_i}$. It is guaranteed that $0 < p_1 < p_2 < \dots < p_{s_i} < d$.

Output Format

Output $n - 1$ lines, each containing one integer: your answer.

3 10
2 4 7
3 3 6 8
1 5

4
6

见附件

6252500
6252500

见附件

999990000
999990000
999990000
999990000

生成器：/paste/3igmip11

生成器：/paste/fusadpm0

Hint

For all testdata, $2 \leq n \leq 500000$, $2 \leq d \leq 10^{12}$, $\sum s_i \leq 500000$.

Translated by ChatGPT 5