该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

岩石怪物杜达生活在魔法森林中，他靠吃能量石来获取能量。

现在，他的能量已经为 0。于是他收集了 N 块能量石，吃第 i 块能量石可以获得 Ei 的能量。他要在接下来的 M 天内把能量石全部吃完，而且需要按照收集的顺序（也就是输入的顺序）依次来吃。

每天吃多少块能量石由杜达来任意决定。他也可以选择在某些天不吃能量石。

但他每天的能量都会在晚上的睡梦中流失一半。（如果是奇数则除以 2 向下取整）

他想在 M 天内他睡觉前的能量值最小的那天的能量值尽可能的大。

请你求出这个最大值，并输出每块能量石在哪天被吃掉。

如果有多种方案，则输出字典序最大的方案。

例如：N=5，M=5，Ei 依次为 10，40，13，22，7。则一种方案如下：

五天内的最小能量值为第五天 24，这是所有方案中最小能量值的最大值。

Input

第一行：N M

接下来的 N 行：每行一个整数 Ei

Output

第一行：一个整数，表示 M 天内睡觉前的最小能量值的最大值

接下来的 N 行：每行一个整数 di，代表第 i 块能量石在第 di 天被杜达吃掉。

如果有多种方案，则输出字典序最大的方案。

Sample Input

5 5
10
40
13
22
7

Sample Output

24
1
1
3
4
5

Hint

共 10 个测试点，全部满足：1≤N,M≤50000, 1≤Ei≤1000000

其中：