Chocolate Cake

There is a round cake made of $2N$ fan-shaped pieces of the same size and area. The pieces are numbered $1$ to $2N$ in clockwise order, and initially the taste of piece $i$ is $A_i$.

Chaewan and Heewon want to split the cake in half. To cut the cake, Chaewan picks one integer $k$ with $1 \le k \le N$, then divides the cake into the part containing pieces $k, k + 1, \cdots, k + N - 1$ and the part containing the remaining pieces. The taste of each part is the sum of the tastes of the pieces it contains.

Chaewan wants to eat the tastier part, so he will choose, among the $N$ possible cuts, the one that maximizes the difference between the tastes of the two parts.

Heewon sees through this plan. He can place chocolate toppings on the pieces so that the difference between the two parts is as small as possible after Chaewan cuts the cake. Each topping placed on a piece raises that piece's taste by $M$. A piece can get several toppings, and several pieces can get toppings at the same time. However, the maximum number of toppings on a single piece is $10^{12}$.

Find a way to place the toppings so that Heewon can split the cake as evenly as possible.

The first line contains two integers $N$ and $M$ separated by a space. $(1 \le N \le 100\ 000$; $1 \le M \le 10^6)$

The next line contains integers $A_1$, $A_2$, $\cdots$, $A_{2N-1}$, $A_{2N}$ separated by spaces. $(1 \le A_i \le 10^6)$

On the first line, print the smallest possible difference in taste.

On the next line, print $2N$ integers $C_1$, $C_2$, $\cdots$, $C_{2N-1}$, $C_{2N}$ separated by spaces. $C_i$ is the number of chocolate toppings placed on piece $i$, and it must satisfy $0 \le C_i \le 10^{12}$. The minimum difference can always be reached within these limits.

If several outputs reach the minimum, print any of them.