The Bajtocki National Theatre is preparing for the premiere of a play titled Les Bitérables. It is high time to take care of the stage design required for the performance. You have received instructions from the director on how to prepare the stage design for each act of the play. Your task is to develop a plan that will help change the stage design between acts as quickly as possible.

For each act, you have received a description of the locations on the stage where stage elements should appear. The elements being placed are very similar to each other (after all, they are all just some "bito-bushes"), so it does not matter which element appears in which location, as long as it is a location designated by the director. We also assume that two stage elements will never appear at the same position during a single act.

Not every act will require all stage elements. Unused elements should be stored backstage. The stage, along with the backstage area, can be represented as the interval $[0, d]$, where positions $0$ and $d$ are backstage areas, and the remaining integer positions represent locations on the stage.

Unfortunately, only one technician will be responsible for changing the stage design, and all stage elements are so heavy that they can only carry one element at a time. Moving a stage element during an intermission (the break between acts) from position $i$ to position $j$ will take the technician $|i - j|$ seconds, while moving around the stage otherwise takes a negligible amount of time. Develop a plan for changing the stage design between acts so that each intermission lasts as short as possible. A large number of stage elements have been prepared for the performance, so the technician will find the required elements backstage if needed.

Input

The first line of the input contains two integers $n$ and $d$ ($2 \le n \le 500\,000$; $2 \le d \le 10^{12}$), representing the number of acts of the play and the length of the Bajtocki National Theatre stage, respectively.

Each of the next $n$ lines contains a non-negative integer $s_i$, representing the number of stage elements needed in the $i$-th act, followed by an increasing sequence of $s_i$ integers $p_1, p_2, \dots, p_{s_i}$ ($0 < p_1 < p_2 < \dots < p_{s_i} < d$), representing the positions where these elements must be placed.

The sum of all values $s_i$ does not exceed $500\,000$.

Output

You should output $n - 1$ lines; the $i$-th line should contain a single integer representing the minimum time in seconds required to perform all necessary changes to prepare the stage design between act $i$ and act $i + 1$.

Examples

Input 1

3 10
2 4 7
3 3 6 8
1 5

Output 1

4
6

Note 1

During the first intermission, the following elements must be moved: from position $4$ to position $3$, from position $7$ to position $6$, and from backstage (position $10$) to position $8$. Thus, the time required to perform the changes is $4$ seconds.

During the second intermission, the following elements must be moved: from position $3$ to backstage (position $0$), from position $6$ to position $5$, and from position $8$ to backstage (position $10$). Therefore, the required time is $6$ seconds.

Evaluation tests

• Test 1: $n = 3, d = 5001$; in the first and third acts no elements are needed, in the second act $5000$ elements must be placed at positions $1, 2, \dots, 5000$.
• Test 2: $n = 5, d = 10^{10}$; in the $j$-th act elements are needed at positions $10^5 \cdot i + 10^4 \cdot j$ for $1 \le i < 10^5, 1 \le j \le 5$.
• Test 3: $n = 500\,000, d = 10^{12}$; in the $i$-th act there is one element at position $(i^i \pmod{d - 1}) + 1$ for $1 \le i \le 500\,000$.

Subtasks