지하철

지하철 노선에 열차 $T$대가 운행하고 있습니다. 모든 열차가 똑같은 간격으로 배치되어 있으면 이상적이며, 이때 운행이 규칙적이라고 말합니다. 하지만 여러 가지 이유로 열차들은 서로 가까워지거나 멀어지곤 합니다. 그래서 가끔 모든 열차에게 잠시 멈춰 몇 분간 기다리라고 요청합니다. 이 과정을 정규화라고 부릅니다.

이웃한 모든 열차 사이의 간격(분 단위)이 주어집니다. 운행이 규칙적이 되어, 이웃한 모든 열차 사이의 간격이 정확히 $M$분이 되도록 하려면 각 열차가 몇 분씩 기다려야 하는지 구하세요.

열차를 멈춰 세워 두는 것은 비용이 크므로, 가능한 답이 여러 개라면 전체 대기 시간의 합이 가장 작은 답을 출력하세요.

첫째 줄에 정수 두 개가 주어집니다. $T$는 열차의 수, $M$은 이웃한 모든 열차 사이의 목표 간격입니다.

둘째 줄에 $T-1$개의 정수 $m_1, m_2, \ldots, m_{T-1}$이 주어집니다. 이는 지하철 노선에서 이웃한 열차 사이의 간격입니다.

한 줄에 $T$개의 정수를 출력합니다. 운행이 규칙적이 되어(모든 간격이 $M$과 같아져) 전체 대기 시간의 합이 최소가 되도록 각 열차가 몇 분씩 기다려야 하는지를 나타냅니다. 이 답은 유일합니다.

• $1 < T \le 100\,000$
• $1 \le m_1, m_2, \ldots, m_{T-1}, M \le 1\,000$