说明

小明和小科在玩数组折叠游戏，游戏规则是，给出n个整数，按照从左到右的顺序排列，现在需要将这列整数从中间折叠m次，左边的叠加到右边，每次折叠后，重合的两个数字会相加变成一个新的数字。请你输出折叠m次后的s数组。

输入格式

第1行：输入一个整数n表示序列的长度，输入一个整数m表示折叠的次数。<o:p></o:p>

第2行：输入n个空格隔开的整数，整数不超过100。

输出格式

样例

5 2
1 2 3 4 5

6 9