Minimum Transportation Cost for Configuration Transformation

You are given an integer \(t\) representing the number of time instants and an integer \(d\) representing the endpoint of a one-dimensional axis \([0,d]\). At each time instant \(i\) (\(1 \le i \le t\)), you are given a configuration of items on the axis in the open interval \((0,d)\): the positions \(p_1, p_2, \dots, p_{s_i}\) where items are present. It is guaranteed that these are the only positions (in \((0,d)\)) that contain items. In addition, there are infinitely many items available at the two endpoints 0 and \(d\).

You can pay a cost of 1 to move any one item one unit to the left or right along the axis. In one operation, the item moves from its current position \(x\) to \(x-1\) or \(x+1\) with a cost of \(1\) per step.

For every pair of consecutive time instants, you need to transform the configuration at the earlier time into the configuration at the later time. That is, given configuration \(A = \{a_1,a_2, \dots, a_n\}\) and configuration \(B = \{b_1,b_2, \dots, b_m\}\) (the orders of \(a_i\) and \(b_j\) can be arbitrary), you want to achieve: after some moves, the items in the open interval \((0,d)\) are exactly those at positions in \(B\).

You are allowed to:

• Move an item from a position \(x\) (either from the previous configuration if \(x\) is in \(A\)) to cover a needed target position \(y\) in \(B\) at a cost of \(|x - y|\).
• If an item from \(A\) is not needed in \(B\), you can move it to one of the endpoints (0 or \(d\)). The cost to remove an item at position \(x\) is \(\min(x,\,d-x)\).
• If a target position \(y\) in \(B\) is not covered by any item from \(A\), you can bring an item from one of the endpoints. The cost to add an item from an endpoint to position \(y\) is \(\min(y,\,d-y)\), where the choice of endpoint is made to minimize the cost.

Compute the minimum total cost required to transform the configuration from one time instant to the next, for every adjacent pair of time instants.

inputFormat

The first line contains two integers \(t\) and \(d\) \((2 \le t,\; d \ge 1)\) where \(t\) is the number of time instants and \(d\) is the endpoint of the axis \([0,d]\).

Then \(t\) blocks follow. For each time instant, the first integer \(s_i\) denotes the number of items in the open interval \((0,d)\). This is followed by \(s_i\) integers \(p_1, p_2, \dots, p_{s_i}\) (\(0 < p_j < d\)) representing the positions where the items are placed. The positions in each block may not be sorted.

outputFormat

Output \(t-1\) lines. The \(i\)-th line should contain a single integer: the minimum cost required to transform the configuration from the \(i\)-th time instant to the \((i+1)\)-th time instant.

sample

2 10
2 2 5
2 3 7

3