背景

wind发明了一个好玩的游戏，叫全班同学一起玩。(p1202)
但小杉玩了十几盘，总是输，终于被大家给踢了出来……
-_-!

描述

这个游戏是这样的，wind先写下一排数。既然是一排，当然有首尾咯。

所有参加的同学轮流取数，每个人每次只能从这排数的头或尾取一个数。

最后谁取的数的和多，谁就赢了。

同学们的智商是很高的（怪不得小杉一直输），你必须知道每个同学总是做出最优决策。

小杉他们班有41个人（小杉太差，不准参加……）。

但有个同学偷偷告诉小杉，大家从一开始就知道自己能拿到的和是多少。

小杉也想知道。

格式

输入格式

每组测试数据的
第一行有两个数n(n<=1000)和k(k<=(41-1))，k表示有多少个同学参加了这个游戏
第二行有n个数，是wind给出的一排数。这n个数均不超过1e6

输出格式

对每组测试数据输出k行，每行一个整数
第i行的输出表示第i个开始取数的人最终能取到多少和

样例1

样例输入1

1 1
1

样例输出1

1

限制

每个测试点1s

提示

注意：小杉的同学们在同等条件下总是先取这排数右边的数

来源

lolanv