You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

acm和超算实验室一起招新啦！

Description

在《并行程序设计导论》这本书当中提到：一个串行程序的高效并行实现可能不是通过发掘其中每一个步骤的高效并行实现来获得，相反，最好的并行可能是通过一步步回溯，然后发现一个全新的算法来获得的。举个例子来说，假设我们需要计算n个数的值再累加求和，如下是串行代码：

现在我们假设有p个核，且p远小于n，那么每个核能够大约计算n/p个数的值并累加求和，以得到部分和：

此处的前缀my_代表每个核都使用自己的私有变量，并且每个核能够独立于其他核来执行该代码块。每个核都执行完代码后，变量my_sum中就会储存调用Compute_next_value获得的值的和。例如，假如有8个核，n=24次调用Compute_next_value获得如下的值

那么储存在my_sum中的值将是：

这里，我们假定用非负整数，0，1，，，，p-1来表示各个核，p是核的总数。当各个核都计算完各自的my_sum值后，将自己的结果值发生给一个指定为“master”的核（主核），master核将收到的部分和累加而得到全局总和：

在我们的例子中，假如master核是0号核，那么它将部分累加求全局综合8+19+7+15+7+13+12+14=95。但是当核数比较多的时候，不再由master核计算所有部分的累加工作，可以将各个核两辆结对，0号核将自己的部分和与1号核的部分和做加法，依次类推2号核和3号核，4号核和5号核。然后再在偶数和上重复累加以此类推。如下图

上述的改进算法让master核（0号核）承担了更少的工作量。

Format

Input

一个整数n,m分别表示数的总数和核的总数（n是m的倍数，m是2的k次幂）

接下来一行包含n个数，表示每个数的数值

Output

第一行表示每个核子得到的累加和

接下每行表示每次执行相加后我们需要的核子的数值（数与数之间包含一个空格，且所有数据范围在int以内）

Samples

24 8
1 4 3 9 2 8 5 1 1 6 2 7 2 5 0 4 1 8 6 5 1 2 3 9

8 19 7 15 7 13 12 14
27 22 20 26
49 46
95

Limitation

1s, 1024KiB for each test case.