长度为 $m$ 的序列 $[v_1, \dots, v_m]$ 的权值定义如下：
- 若 $m = 1$，则权值为 $v_1$。
- 若 $m > 1$，则权值为序列中最后一个数与前面所有元素的最大值之和，即 $\max_{i=1}^{m-1} v_i + v_m$。
给定一个序列 $a_1, a_2, \dots, a_n$。你希望将其划分为至多 $k$ 个非空子序列，使得这些子序列的权值之和最大。
“子序列”是指从原序列中删除 0 个或多个元素，且不改变剩余元素的相对顺序所得到的序列。
划分后，原序列中的每个元素必须恰好属于一个子序列。
输入格式
第一行包含两个整数 $n$ 和 $k$（$n \ge 2$，$1 \le k \le n \le 2 \times 10^5$）。
第二行包含 $n$ 个整数 $a_i$（$-10^9 \le a_i \le 10^9$）。
输出格式
输出两行。
第一行包含一个整数，表示划分得到的子序列权值之和的最大可能值。
第二行包含 $n$ 个整数 $id_i$（$1 \le id_i \le k$），其中具有相同 $id_i$ 的元素被分配到同一个子序列中。由于我们不要求恰好有 $k$ 个非空子序列，因此不要求 $1$ 到 $k$ 之间的每个整数都出现在 $id_i$ 中。
样例
输入样例 1
7 2 6 3 7 5 6 4 5
输出样例 1
24 1 2 2 1 1 2 2
输入样例 2
5 2 -5 -4 -3 -2 -1
输出样例 2
-3 1 1 1 1 1
说明
在第一个样例中，一种可能的划分是将其分为两个子序列：$[a_1, a_4, a_5] = [6, 5, 6]$ 和 $[a_2, a_3, a_6, a_7] = [3, 7, 4, 5]$。它们的权值之和为 $12 + 12 = 24$。