30789번 - 초콜릿 케이크 스페셜 저지

문제

2ドルN$개의 크기와 넓이가 같은 부채꼴 모양 조각으로 이루어진 원형 케이크가 있다. 각 조각은 시계 방향으로 1ドル$번부터 2ドルN$번까지 순서대로 번호가 붙어 있으며, 처음에 $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)$

출력

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

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

최솟값을 달성할 수 있는 출력이 여러 가지인 경우 그중 아무거나 출력한다.

제한

힌트