프리모니다스 왕은 온 땅에서 가장 강한 검투사를 찾기 위해 토너먼트를 개최하고 있습니다. 고향에 명예와 영광을 안겨주기 위해 총 $N$명의 검투사가 콜로세움에 모였습니다. 각 검투사는 일정량의 활력(vitality)을 가지고 시작합니다. 활력은 검투사가 견딜 수 있는 피해량을 나타낸다는 점에서 체력(HP)과 비슷하지만, 강한 일격을 가하는 데에는 에너지가 필요하므로 검투사가 가할 수 있는 피해량을 나타내기도 합니다.

토너먼트는 $K$개의 라운드로 진행됩니다. 매 라운드마다 왕은 검투사들을 남은 활력이 가장 적은 사람부터 가장 많은 사람까지 일렬로 세우며, 활력이 같은 경우 무작위로 순서를 정합니다. 프리모니다스 왕은 검투사의 진정한 강함이 공격을 버텨내는 능력에 있다고 믿기 때문에, 첫 번째 검투사(남은 활력이 가장 적은 검투사)에게 두 번째 검투사를 향해 자신의 가장 강한 일격을 가하라고 명령합니다. 이 일격은 두 번째 검투사의 활력에서 첫 번째 검투사의 활력을 뺍니다. 두 번째 검투사는 공격을 받은 뒤, (낮아진 새로운 활력을 사용하여) 세 번째 검투사에게 자신의 가장 강한 일격을 가하며, 이 과정이 차례대로 이어집니다. 이 과정은 뒤에서 두 번째 검투사가 마지막 검투사(아무도 공격할 수 없는 검투사)에게 가장 강한 일격을 가할 때까지 반복됩니다.

위 과정에서 검투사의 활력은 절대 0 미만으로 내려가지 않는다는 점에 유의하십시오. (활력이 0인 검투사는 다음 검투사에게 피해가 전혀 없는 미약한 일격을 가합니다.)

$K$번의 토너먼트 라운드가 끝난 후 각 검투사의 활력을 줄의 첫 번째 검투사부터 마지막 검투사까지 순서대로 출력하십시오.

입력

입력의 첫째 줄에 검투사의 수와 토너먼트의 라운드 수를 나타내는 두 정수 $N$ ($2 \le N \le 10^5$)과 $K$ ($1 \le K \le 10^{18}$)가 공백으로 구분되어 주어집니다.

다음 줄에 검투사들의 초기 활력을 나타내는 $N$개의 정수 $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$)이 공백으로 구분되어 주어집니다.

출력

토너먼트의 $K$번째 라운드가 끝났을 때 검투사들의 활력을 현재 줄에 서 있는 순서대로 공백으로 구분하여 $N$개의 정수로 출력합니다.

예제

입력 1

6 3
21 28 24 23 1 12

출력 1

1 1 3 6 3 10

입력 2

3 1000
8 2 10

출력 2

0 0 2