초콜릿 케이크

$2N$개의 크기와 넓이가 같은 부채꼴 모양 조각으로 이루어진 원형 케이크가 있다. 각 조각은 시계 방향으로 $1$번부터 $2N$번까지 순서대로 번호가 붙어 있으며, 처음에 $i$번 조각의 맛은 $A_i$이다.

채완이는 희원이와 케이크를 절반으로 잘라 나눠 먹으려고 한다. 케이크를 자를 때는 $1$ 이상 $N$ 이하의 정수 $k$를 하나 고른 뒤, 케이크를 $k$, $k + 1$, $\cdots$, $k + N - 1$번 조각이 포함된 부분과 그렇지 않은 부분으로 나눈다. 나눠진 각 부분의 맛은 그 부분에 포함된 케이크 조각 맛의 합으로 정한다.

채완이는 더 맛있는 부분을 먹고 싶어 하므로, 케이크를 자르는 $N$가지 방법 중 두 부분의 맛 차이가 최대가 되는 방법을 고른다.

희원이는 이 계략을 간파하고, 채완이가 케이크를 잘랐을 때 두 부분의 맛 차이가 최소가 되도록 케이크 조각 위에 초콜릿 토핑을 올려두려고 한다. 어떤 조각에 토핑을 하나 올리면 그 조각의 맛은 $M$만큼 올라간다. 한 조각에 여러 개의 토핑을 올릴 수 있고, 여러 조각에 동시에 올릴 수도 있다. 다만 한 조각에 올릴 수 있는 초콜릿의 최대 개수는 $10^{12}$개이다.

희원이가 케이크를 최대한 공평하게 나눠 먹을 수 있도록, 각 조각에 초콜릿 토핑을 올리는 방법을 구하라.

첫째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 100\ 000$; $1 \le M \le 10^6)$

다음 줄에 정수 $A_1$, $A_2$, $\cdots$, $A_{2N-1}$, $A_{2N}$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^6)$

첫째 줄에 가능한 맛 차이의 최솟값을 출력한다.

다음 줄에 $2N$개의 정수 $C_1$, $C_2$, $\cdots$, $C_{2N-1}$, $C_{2N}$을 공백으로 구분하여 출력한다. $C_i$는 $i$번 조각에 올려놓을 초콜릿의 개수이며, $0 \le C_i \le 10^{12}$을 만족해야 한다. 주어진 범위 안에서 항상 맛 차이를 최소화할 수 있다.

최솟값을 달성하는 출력이 여러 가지라면 그중 아무거나 출력한다.