题目描述

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

输入格式

第1行是整数n和m;第2行是数组中的n个整数

输出格式

为1行。折叠m次后的数组

样例

输入样例 1

3 1
1 2 3

输出样例 1

4 2

输入样例 2

5 2
1 2 3 5 6

输出样例 2

10 7

输入样例 3

7 3
4 2 6 8 7 9 1

输出样例 3

37