P9403 [POI 2020/2021 R3] Les Bitérables

Translated from [XXVIII Olimpiada Informatyczna - Stage III](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Les Bitérables](https://szkopul.edu.pl/problemset/problem/Lpz563_ATiESIrNZxiT5bwIx/statement/). d1t2。

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.

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 $n - 1$ lines, each containing one integer: your answer.

For all testdata, $2 \leq n \leq 500000$, $2 \leq d \leq 10^{12}$, $\sum s_i \leq 500000$. | Subtask ID | Additional Constraints | Score | | :----------: | :----------: | :----------: | | 1 | $s_i \leq 1$ | 5 | | 2 | $s_i \leq 3$ | 10 | | 3 | $d \leq 7$ | 12 | | 4 | $\sum s_i \leq 5000$ | 27 | | 5 | If $s_i > 0$, then $p_{s_i} = p_1 + s_i - 1$ | 11 | | 6 | | 35 | Translated by ChatGPT 5