\(N\) 개의 물탱크가 한 줄로 놓여 있고, 왼쪽부터 \(i\) 번째 탱크에는 \(A_i\) 리터의 물이 들어 있다.

이 시스템은 총 \(T\) 단계 동안 작동한다. 한 단계 동안 인접한 모든 쌍 \((i, i+1)\) 은 동시에 다음 규칙에 따라 물을 주고받는다.

• 두 탱크의 수위 차이 \(d = |A_i - A_{i+1}|\) 를 본다.
• 더 많이 든 탱크가 더 적게 든 탱크에게 \(\lfloor d / 2 \rfloor\) 리터를 보낸다. (차이가 \(0\) 또는 \(1\) 이면 아무것도 보내지 않는다.)

한 단계 안의 모든 이동량은 그 단계가 시작될 때의 수위를 기준으로 동시에 계산되므로, 쌍을 처리하는 순서는 결과에 영향을 주지 않는다.

예를 들어 탱크가 \([10, 0, 0, 0]\) 인 상태에서 한 단계를 진행하면 첫 쌍 \((1, 2)\) 만 \(\lfloor 10/2 \rfloor = 5\) 를 이동시켜 \([5, 5, 0, 0]\) 이 된다.

\(T\) 단계가 모두 끝난 뒤 각 탱크의 물의 양을 출력하는 프로그램을 작성하라.

\(1 \le N \le 1{,}000\)

\(0 \le T \le 100{,}000\)

\(0 \le A_i \le 1{,}000{,}000\)

물의 총량은 항상 보존된다.

첫째 줄에 두 정수 \(N\) 과 \(T\) 가 주어진다 (\(1 \le N \le 1{,}000\), \(0 \le T \le 100{,}000\)).

둘째 줄에 \(N\) 개의 정수 \(A_1, A_2, \dots, A_N\) 이 공백으로 구분되어 주어진다 (\(0 \le A_i \le 1{,}000{,}000\)).

한 줄에 \(T\) 단계가 모두 끝난 뒤 각 탱크의 물의 양을 왼쪽부터 차례대로 공백으로 구분하여 출력한다.

riseoj 작성

출처 Original