描述

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

输入

• 第1行是两个整数n和m，表示数组的长度和折叠次数。
• 第2行是数组中的n个整数。

输出

一行，表示折叠m次后的数组。

样例输入

3 1
1 2 3

样例输出

4 2

数据范围

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ 10
• 1 ≤ 每个元素的值 ≤ 1000